Parity Is Not in AC^0

Symptom

You have just read T030 and you are demoralized. Relativization kills the techniques that treat machines as black boxes. Natural proofs kill the combinatorial ones, assuming pseudorandom functions exist. Between them they appear to rule out everything anyone knows how to do, and the honest summary of fifty years is that nobody can prove any interesting problem is hard.

Except that summary is wrong, and believing it is the reason people leave this field.

Here is a problem: given $n$ input bits, output their XOR. It is trivial — one line of code, and a chain of $n-1$ XOR gates computes it with $n$ gates.

Now add one constraint. Your circuit has AND and OR gates of unbounded fan-in, so a single gate can read all $n$ inputs at once, plus free NOT gates. The only restriction is constant depth: a fixed number of layers, independent of $n$.

You cannot do it. Not with a clever encoding, not with a million gates. Any constant-depth circuit computing parity needs exponentially many gates, and this is not a conjecture. It is proved, unconditionally, with no assumptions about anything.

Statement

$\mathsf{AC}^0$ is the class of languages decided by circuit families of constant depth and polynomial size, over unbounded fan-in AND, OR, and NOT.

Parity is not in $\mathsf{AC}^0$. Any depth-$d$ circuit computing the parity of $n$ bits requires at least $2^{\Omega(n^{1/(d-1)})}$ gates.

Two things deserve emphasis.

It is unconditional. No assumption that $\mathsf{P} \ne \mathsf{NP}$, no cryptographic hypothesis, no oracle. This is a theorem in the same sense that the pigeonhole principle is a theorem.

It is tight. The bound is matched by a construction, so this is the exact answer rather than the best current lower bound.

Put numbers on it. At $n = 1000$ and depth 3, the exponent $n^{1/2}$ is about 31.6, so you need roughly $2^{31.6} \approx 3.3 \times 10^9$ gates to XOR a thousand bits in three layers. At depth 5 the exponent drops to about 5.6 and the bound becomes vacuous, which is exactly what “constant depth costs exponentially” means: buying one more layer is worth an enormous amount, and no fixed number of layers is ever enough.

Argument

The proof is Håstad’s switching lemma, and the strategy is to attack the circuit rather than the function.

The setup. Assume a depth-$d$, size-$S$ circuit computes parity. Normalize it so the bottom layer consists of small-width AND gates (a DNF at the bottom).

The move: random restriction. Pick each input independently. With probability $p$ leave it free; otherwise fix it to 0 or 1 at random. This kills most inputs and simplifies the circuit drastically.

The lemma. If a function is computed by a width-$w$ DNF, then after a random restriction keeping each variable free with probability $p$, the restricted function is computed by a width-$k$ CNF — except with probability at most $(5pw)^k$.

That is the whole engine, and the point is the swap. An OR of ANDs becomes an AND of ORs. Once the bottom two layers are both ANDs, they merge into one, and the circuit’s depth drops by one at the cost of a probability penalty.

The induction. Apply the lemma repeatedly with $p \approx 1/(10w)$ at each stage. Each application costs one layer. After $d-2$ applications the circuit has collapsed to depth 2 — a single small-width DNF or CNF — and a union bound over all $S$ gates keeps the total failure probability below 1, so some restriction achieves every collapse simultaneously.

The contradiction. Parity has a property nothing else has: every restriction of parity is parity or its negation, on the surviving variables. Fixing some inputs never simplifies it, because every remaining variable still flips the answer. So if enough variables survive — and with $p$ chosen as above, about $n^{1/(d-1)}$ do — the collapsed depth-2 circuit must compute parity on them.

But a depth-2 circuit computing parity on $m$ variables needs width $m$: any term of width less than $m$ leaves a variable free, and that variable flips the output, so the term cannot be decisive. A width-$m$ DNF needs $2^{m-1}$ terms.

Since we assumed the circuit was small, contradiction, and the surviving count $m \approx n^{1/(d-1)}$ is exactly where the bound’s shape comes from. $\blacksquare$

Why this evades the barriers of T030. Relativization does not apply because circuit lower bounds are not statements about oracle machines — there is no machine to relativize. Natural proofs does not apply because the switching lemma argument is not large: the property “is not simplified by any restriction” is satisfied by essentially no functions, whereas a natural proof requires a property that most functions have. The proof exploits a highly specific structural feature of parity, and that specificity is what lets it through.

This is the reason the post exists. The barriers rule out entire families of technique, not the possibility of progress, and $\mathsf{AC}^0$ is the standing proof that unconditional lower bounds against real computational models are obtainable.

A second reading of the same fact: parity has no low-degree approximation. Razborov and Smolensky’s route to the same conclusion is worth carrying because it generalizes further. Represent each gate by a polynomial over $\mathbb{F}_2$ that agrees with it on most inputs. An unbounded fan-in OR of $n$ inputs is approximable by a polynomial of degree $O(\log n)$ by randomly subsampling the inputs, so a depth-$d$ circuit of size $S$ is approximable by a polynomial of degree $(\log S)^d$, agreeing with the circuit on most inputs.

Now compute parity’s degree. Over $\mathbb{F}_2$, parity is the degree-1 polynomial $x_1 + \cdots + x_n$, so that field is useless. Move to $\mathbb{F}_3$, encode bits as $\pm 1$, and parity becomes the product $\prod x_i$, which has degree $n$ and provably admits no approximation of degree below $\sqrt{n}$ on more than a small fraction of inputs. Setting $(\log S)^d < \sqrt{n}$ gives $S > 2^{n^{1/(2d)}}$ — the same shape of bound from a completely different technique.

Two independent proofs matter here for the same reason two independent measurements matter. It is not a fluke of one clever argument, and the polynomial method is what extends to $\mathsf{AC}^0[p]$ for prime $p$, which is why the wall at composite modulus is precisely where $\mathbb{Z}/6$ stops being a field.

Forbids

Constant-depth polynomial-size circuits for parity, and hence for anything parity reduces to: majority, sorting, integer multiplication, and connectivity are all outside $\mathsf{AC}^0$ by consequence.

A polynomial-size constant-depth CRCW PRAM algorithm for parity. The $\mathsf{AC}^0$ class corresponds exactly to constant-time PRAM computation with polynomially many processors, so this is a genuine parallel-computing lower bound: XOR cannot be done in $O(1)$ parallel time with polynomial hardware.

Certain circuit designs, physically. A parity tree over 64 bits has logarithmic depth for a reason, and no layout trick flattens it. Every carry chain and every ECC syndrome generator in silicon pays this depth, which is why carry-lookahead adders buy depth with area and cannot buy it down to constant.

Hope that $\mathsf{AC}^0$ captures useful computation. It contains addition and comparison, and stops almost immediately after.

Does not forbid

It does not forbid fast parity in hardware, which is the misreading that makes people think the theorem is wrong. Your CPU has a parity flag and computes it in one cycle. POPCNT counts set bits in a 64-bit word in a single instruction. There is no contradiction: $n$ is fixed at 64, and “constant depth, polynomial size” is an asymptotic statement about a family of circuits. The theorem says depth must grow with $n$, and 64-bit hardware uses a fixed logarithmic-depth tree of six layers. Fixed-width hardware never feels an asymptotic bound.

It does not forbid parity in slightly larger classes, and the boundary is startlingly sharp. $\mathsf{AC}^0[\oplus]$ — the same circuits plus MOD-2 gates — contains parity by definition. $\mathsf{NC}^1$, allowing logarithmic depth with bounded fan-in, contains it easily. Razborov and Smolensky extended the result to $\mathsf{AC}^0[p]$ for prime $p$, and then progress stopped: nobody can prove a lower bound against $\mathsf{ACC}^0$ with composite modulus, say MOD-6 gates. Williams’ 2011 result separating $\mathsf{NEXP}$ from $\mathsf{ACC}^0$ was celebrated precisely because that wall had stood for twenty-five years.

It does not mean lower bounds are easy now. The distance from $\mathsf{AC}^0$ to $\mathsf{P}$ is enormous, and the current frontier for general circuits is embarrassing: the best known lower bound for an explicit function in $\mathsf{NP}$ is around $5n$ gates. Five times $n$. Proving anything superlinear for general circuits is open.

It does not make parity hard in any practical sense. It is $O(n)$ time, $O(\log n)$ depth, and about as cheap as computation gets. The theorem is about one specific restricted model, and “not in $\mathsf{AC}^0$” is a statement about parallel depth rather than about difficulty.

It does not rely on any unproven assumption, unlike almost everything else in Part IV. If you take one structural fact from this post, it is that this result would survive a proof that $\mathsf{P} = \mathsf{NP}$ tomorrow.

Boundary

The result is exactly about constant depth with unbounded fan-in, and every neighbouring model behaves differently:

• Add MOD-$p$ gates ($\mathsf{AC}^0[p]$, prime $p$): Razborov-Smolensky still gives lower bounds, by approximating circuits with low-degree polynomials over $\mathbb{F}_p$.
• Composite modulus ($\mathsf{ACC}^0$): open, and the polynomial method breaks because $\mathbb{Z}/6$ is not a field. This is the current frontier.
• Logarithmic depth, bounded fan-in ($\mathsf{NC}^1$): parity is in, and no separation from $\mathsf{P}$ is known.
• Threshold gates ($\mathsf{TC}^0$): parity is in, and this matters practically because $\mathsf{TC}^0$ is essentially constant-depth neural networks. The reason a small transformer struggles to learn parity while learning far more complex-looking functions easily is this hierarchy showing through, and it is a live thread in the length-generalization literature.

What the theorem ultimately provides is a proof of concept. The barriers say certain techniques cannot work; $\mathsf{AC}^0$ says lower bounds themselves are attainable when you find a structural handle. The field is not stuck for lack of possibility. It is stuck for lack of handles.

Read next