Parity is not in AC0

Remarks

Part 1 was proved by Furst, Saxe and Sipser and independently by Ajtai, and part 2 is due to Håstad. The proof uses random restrictions: fix each input at random to $0$ or $1$, except for a small random set of inputs left free. Håstad's switching lemma says that after such a restriction a small-width DNF becomes, with high probability, a small-width CNF. Then one layer of the circuit can be merged into the next. After $d - 2$ rounds the circuit depends on few of the free variables. But the restriction of parity to the free variables is still parity or its negation, and it depends on all of them.

The bound in part 2 is sharp up to the constant $\varepsilon_d$: parity has depth-$d$ circuits of size $2^{O(n^{1/(d-1)})}$. The constant depth is necessary: with depth $O(\log n)$, a balanced tree of exclusive-or blocks computes parity with $O(n)$ gates.

Going deeper

For a student

This was one of the first unconditional lower bounds for a natural model of computation. It separates $\mathrm{AC}^0$ from $\mathrm{NC}^1$, since parity is in NC at level $1$. Razborov and Smolensky gave a second proof by approximating $\mathrm{AC}^0$ circuits with low-degree polynomials over a finite field. Their method also shows that counting modulo a prime $q$ is not in $\mathrm{AC}^0$ with gates counting modulo a different prime $p$. The proof is natural in the sense of the natural proofs barrier, which explains why such methods do not reach general circuits.