arXiv · Sep 30, 2026
Top-Down Lower Bounds for All Depths
By Oliver Korten
We prove that Parity requires 2^n^(Ω(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(ε_d n^(1/(2d-2))) for some ε_d>0 depending only on d, and the second achieving the essentially tight lower bound exp(ε_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}ⁿ will look close to uniform after projecting it onto a random small set of coordinates R subseteq [n].