Parity function needs very large circuits at all constant depths
Top-Down Lower Bounds for All Depths
Computational Complexity
Summary
The paper shows that solving the parity problem (determining if a list of bits has an even or odd number of ones) requires very large logical circuits if those circuits have a fixed small number of layers. The authors build on previous work and extend methods to prove stronger size limitations for circuits of any constant depth. Their key insight involves understanding how certain random projections of data behave like uniform randomness, which helps them show why small circuits can’t work well. This advances our understanding of limits on efficient circuit designs.
What this means in practice
- •For hardware designers: Clarifies the inherent complexity limits of designing fast logical circuits for parity-related tasks at fixed depths.
- •For cryptography engineers: Provides deeper theoretical limits on circuit simplifications that impact cryptographic function implementations reliant on parity computations.
A theory result. No direct application yet.
Authors
Oliver Korten
Abstract
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\}^n$ will look close to uniform after projecting it onto a random small set of coordinates $R \subseteq [n]$.