Top-Down Lower Bounds for All Depths

Abstract

We prove that Parity requires $2^{n^{\Omega (1)}}$ size De Morgan circuits of constant depth using a new method which is completely "top-down" in the sense of [HJP95]. The proof relies crucially on the core ideas developed in a line of work [HJP95, PPZ99, MW19, GRSS24] which previously established top-down lower bounds for circuits of depth 3 and 4. We first present a proof of a lower bound $\exp (n^{3^{-d}})$. In this case, nearly all of the relevant combinatorial ideas necessary for the proof are already present in some form in [GRSS24]. We then present two extensions of this argument, the first achieving a lower bound $\exp ({\epsilon }_d{n}^{1/(2d-2)})$ for some ${\epsilon }_d>0$ depending only on $d$, and the second achieving the essentially tight lower bound $\exp ({\epsilon }_d{n}^{1/(d-1)})$. These improved results each hinge on establishing a key lemma which quantifies the extent to which a high entropy random variable in $\{0,1{\}}^n$ will look close to uniform after projecting it onto a random small set of coordinates $R\subseteq [n]$.

arXiv comment20 pages