Theory of Computing
-------------------
Title     : Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
Authors   : Yuval Filmus, Or Meir, and Avishay Tal
Volume    : 19
Number    : 7
Pages     : 1-51
URL       : https://theoryofcomputing.org/articles/v019a007

Abstract
--------

Hastad 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{\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 Hastad to hold under
a far wider family of random restrictions and their generalization --
random projections. Based on our shrinkage results, we obtain an
$\tilde{\Omega}(n^{3})$ formula size lower bound for an explicit
function computable in $AC^0$. This improves upon the best known
formula size lower bounds for $AC^0$, 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 $AC^0$ 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 Hastad'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 Hastad's result.


-----------------

An extended abstract of this article appeared in the 
Proceeding of the 12th Innovations in Theoretical
Computer Science Conference (ITCS'21).