English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

H\r{a}stad showed that any De Morgan formula (composed of AND, OR and NOTgates) shrinks by a factor of $O(p^{2})$ under a random restriction that leaveseach variable alive independently with probability $p$ [SICOMP, 1998]. Usingthis result, he gave an $\widetilde{\Omega}(n^{3})$ formula size lower boundfor the Andreev function, which, up to lower order improvements, remains thestate-of-the-art lower bound for any explicit function. In this work, we extendthe shrinkage result of H\r{a}stad to hold under a far wider family of randomrestrictions and their generalization -- random projections. Based on ourshrinkage results, we obtain an $\widetilde{\Omega}(n^{3})$ formula size lowerbound for an explicit function computed in $\mathbf{AC}^0$. This improves uponthe best known formula size lower bounds for $\mathbf{AC}^0$, that were onlyquadratic prior to our work. In addition, we prove that the KRW conjecture[Karchmer et al., Computational Complexity 5(3/4), 1995] holds for innerfunctions for which the unweighted quantum adversary bound is tight. Inparticular, this holds for inner functions with a tight Khrapchenko bound. Ourrandom projections are tailor-made to the function's structure so that thefunction maintains structure even under projection -- using such projections isnecessary, as standard random restrictions simplify $\mathbf{AC}^0$ circuits.In contrast, we show that any De Morgan formula shrinks by a quadratic factorunder our random projections, allowing us to prove the cubic lower bound. Ourproof techniques build on the proof of H\r{a}stad for the simpler case ofbalanced formulas. This allows for a significantly simpler proof at the cost ofslightly worse parameters. As such, when specialized to the case of $p$-randomrestrictions, our proof can be used as an exposition of H\r{a}stad's result.

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathbf{AC}^0$