Shrinkage under Random Projections, and Cubic Formula Lower Bounds for ${\mathsf{A}\mathsf{C}}^0$

$$ H\r{a}stad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of $\tilde{O}(p^2)$ under a random restriction that leaves each variable alive independently with probability $p$ [SICOMP, 1998]. Using this result, he gave an $\tilde{\mathrm{\Omega }}(n^3)$ formula size lower bound for the Andreev function, which, up to lower order improvements, remains the state-of-the-art lower bound for any explicit function. In this paper, we extend the shrinkage result of H\r{a}stad to hold under a far wider family of random restrictions and their generalization – random projections. Based on our shrinkage results, we obtain an $\tilde{\mathrm{\Omega }}(n^3)$ formula size lower bound for an explicit function computable in $\text{ACz}$. This improves upon the best known formula size lower bounds for $\text{ACz}$, that were only quadratic prior to our work. In addition, we prove that the KRW conjecture [Karchmer et al., Computational Complexity 5(3/4), 1995] holds for inner functions for which the unweighted quantum adversary bound is tight. In particular, this holds for inner functions with a tight Khrapchenko bound. Our random projections are tailor-made to the function’s structure so that the function maintains structure even under projection – using such projections is necessary, as standard random restrictions simplify $\text{ACz}$ circuits. In contrast, we show that any De Morgan formula shrinks by a quadratic factor under our random projections, allowing us to prove the cubic lower bound. Our proof techniques build on H\r{a}stad’s proof for the simpler case of balanced formulas. This allows for a significantly simpler proof at the cost of slightly worse parameters. As such, when specialized to the case of $p$-random restrictions, our proof can be used as an exposition of H\r{a}stad’s result.