Shrinkage under Random Projections, and Cubic Formula Lower Bounds for
arXiv:2012.02210 · doi:10.4086/toc.2023.v019a007
Abstract
HÃ¥stad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of under a random restriction that leaves each variable alive independently with probability [SICOMP, 1998]. Using this result, he gave an 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Ã¥stad to hold under a far wider family of random restrictions and their generalization -- random projections. Based on our shrinkage results, we obtain an formula size lower bound for an explicit function computable in $\ACz$. This improves upon the best known formula size lower bounds for $\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 $\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Ã¥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 -random restrictions, our proof can be used as an exposition of HÃ¥stad's result.
Published in Theory of Computing, Volume 19 (2023), Article 7; Received: February 19, 2021, Revised: December 28, 2021, Published: December 5, 2023