The Switching Lemma and Why Parity Needs Depth to Compute

The circuit class $\mathrm{AC}^0$ permits unbounded fan-in AND and OR gates, NOT gates, polynomial size, and constant depth. It contains addition, subtraction, comparison, and every function whose output depends on a bounded number of blocks of the input. It does not contain parity. The proof is a random restriction argument with an unusually clean shape: assign values to most variables at random, observe that the circuit simplifies dramatically, and derive a contradiction from the fact that the function being computed does not simplify at all.

The lemma, stated operationally

A random restriction $\rho$ fixes each variable independently with probability $p$, leaving it free otherwise. Applied to a circuit, the restriction substitutes fixed values, evaluates gates whose inputs have become known, and leaves the rest. The result is a smaller circuit on fewer variables.

The switching lemma bounds what happens to a depth-2 circuit under such a restriction. Let $F$ be a DNF formula — an OR of ANDs — with terms of width at most $w$ over $n$ variables. Apply a random restriction with $p \le 1/(10w)$ and let $t$ be the number of free variables remaining. Then with probability at least $1 - (5pw)^s$, the restricted formula is equivalent to a CNF formula in which each clause has width at most $s$. The parameter $s$ is chosen by the user; the probability of failure is small when $s$ is modest and $p$ is small.

The content is that an OR of ANDs becomes an AND of ORs of bounded width. The direction of the conversion is the whole point: after the restriction, the formula can be represented in the other normal form with a width that does not depend on the original term width. An OR of ANDs is a disjunction, which a depth-2 circuit handles with one wide OR gate; a CNF with bounded clause width is a conjunction of narrow ORs, which is one level up in the dual representation and, crucially, can be merged into the surrounding gate without increasing depth.

The proof counts. For a single term, the probability that the restriction leaves it capable of falsifying a candidate clause is bounded by the probability that it retains enough free variables to do so, which decays geometrically in $p w$. Union-bounding over all terms and all clauses, then choosing the clause width $s$ to balance the two tails, gives the stated bound. Håstad’s contribution was to remove a factor of $w$ from the exponent of the earlier bound of Furst, Saxe and Sipser, and the constant $1/10$ is a convenience, not a sharp threshold.

Applying it to a constant-depth circuit

The proof that parity is outside $\mathrm{AC}^0$ proceeds by contradiction. Suppose a depth-$d$ circuit of size $s$ computes parity on $n$ variables, with $d$ and the size polynomial fixed and $n$ large.

Apply a random restriction with $p = n^{-\alpha}$ for a small constant $\alpha$, chosen so that about $n^{1-\alpha}$ variables remain free. With high probability the restriction simplifies the circuit. Process the circuit bottom-up: each depth-2 block is converted by the switching lemma from the form that feeds an OR gate into the form that feeds an AND gate, so that a gate and its children can be merged into a single gate of the same type one level up. After processing all $d$ levels, the circuit collapses to a single gate — either a wide OR of narrow ANDs or the dual — on the surviving variables.

A single gate of that shape depends on at most $w$ of its inputs in the sense that matters: to determine its output, it suffices to inspect a set of at most $w$ variables, where $w$ is the width accumulated through the conversions. For parity, no such small set determines the output, because flipping any single free variable flips the answer. Formally, parity is not computed by any formula of small width on more than one variable, since every variable is relevant and the function is not constant on any subcube of codimension one.

The contradiction is quantitative. The accumulated width $w$ grows with the number of switching steps and the number of terms, but stays below $n^{1-\alpha}$ for suitable $\alpha$ and $d$, while the number of surviving variables is $n^{1-\alpha}$. For $n$ large enough, the circuit would have to decide parity by inspecting fewer variables than it has, which is impossible.

import random

def restrict_and_evaluate(terms, n, p):
    """terms: list of dicts mapping variable index -> required bit.
    Fixes each variable with probability p; returns (remaining, is_satisfied)."""
    fixed = {}
    for v in range(n):
        if random.random() < p:
            fixed[v] = random.randint(0, 1)

    surviving = []
    for term in terms:
        # A term dies if any of its literals contradicts the assignment.
        if any(v in fixed and fixed[v] != b for v, b in term.items()):
            continue
        # Otherwise keep only the still-free literals.
        surviving.append({v: b for v, b in term.items() if v not in fixed})
    return fixed, surviving

# Under a restriction with p ~ 1/w, terms of width w mostly acquire a fixed
# literal and die; the few survivors are short, which is the switching lemma's
# combinatorial core.

The exponent, and why it is not merely qualitative

The bound that comes out of the argument is not just “parity is not in $\mathrm{AC}^0$” but a size lower bound as a function of depth. For a depth-$d$ circuit computing parity on $n$ variables, size must be at least $2^{\Omega(n^{1/(d-1)})}$. The exponent degrades with depth: depth 3 requires exponential size, depth 4 requires a smaller exponential, and for depth growing with $n$ the bound becomes trivial.

This degradation is the reason the bound does not extend upward on its own. A circuit of depth $\log n$ can compute parity with $O(n)$ gates by building a balanced XOR tree, and the tree’s depth is logarithmic precisely because each level halves the number of unresolved bits. A bound of the shape $2^{n^{1/(d-1)}}$ becomes vacuous once $d$ reaches $n$: the exponent shrinks toward 1 and the bound collapses to a constant. The same collapse happens earlier, at $d \approx \log n$, where $n^{1/(d-1)}$ falls below $\log n$ and the exponential no longer rules out polynomial size. The class $\mathrm{NC}^1$ — polynomial size, logarithmic depth — is exactly where the method stops.

What the lemma does reach

Three results follow from the same machinery and are worth separating from the parity theorem.

$\mathrm{AC}^0$ cannot compute majority either, by the same restriction argument: majority is also sensitive to every variable, and no small-width formula decides it. The class $\mathrm{TC}^0$, which adds majority gates as primitives, is therefore strictly above $\mathrm{AC}^0$, and the depth hierarchy places it there.

$\mathrm{AC}^0$ cannot compute the parity of any function with sufficient structure, which yields the result that integer multiplication is not in $\mathrm{AC}^0$ even restricted to a single output bit, since that bit encodes the parity of a subset of the partial products. The proof composes a parity instance into the multiplication circuit, and composition is what makes the result apply to a subcomputation embedded in a larger circuit.

A related application composes the lemma with the structure of arithmetic circuits. The general principle of the method is that it converts a wide gate into a narrow one at the cost of a probability of failure, and iterating that conversion across depth bounds the total width. Each iteration costs a factor in the failure probability, which is why the number of iterations — the depth — appears in the exponent of the final bound. The fan-in reduction, which trades gate width for depth, is the other half of the picture and is treated in the depth hierarchy.

Where the method breaks, precisely

The switching lemma requires that after restriction, a depth-2 block can be represented in the dual normal form with bounded width. That requirement fails for gates that are not merely wide ANDs and ORs.

Parity gates defeat it immediately. A parity gate on free variables is not equivalent to any small CNF or DNF, because its every clause has width equal to the number of free variables: parity’s CNF representation consists of $2^{k-1}$ clauses of width $k$ over $k$ variables, and no restriction short of fixing all of them reduces the width. This is the algebraic statement of the same obstruction that makes parity hard, and it is why the class $\mathrm{ACC}^0$, which permits parity and modulo gates, resists the method. The known lower bounds for $\mathrm{ACC}^0$ — Williams’ 2011 result that $\mathrm{NEXP}$ is not in $\mathrm{ACC}^0$ — come from a different technique entirely, and the next article discusses why the algebraic approaches are constrained.

Threshold gates defeat it for the same reason. A majority gate on $k$ free variables has no bounded-width representation in either normal form, since its output depends on the exact count of ones. Adding threshold gates gives $\mathrm{TC}^0$, and no switching-lemma argument separates $\mathrm{TC}^0$ from $\mathrm{NC}^1$; that separation is open.

A more basic limitation is that the lemma is a statement about formulas, and its application to circuits requires converting each depth-2 block into a formula. That conversion is free at depth 2 — a DNF is a formula — but the size of the resulting formula is the number of terms times the width, and the union bound over terms is what forces the exponential-in-$n^{1/(d-1)}$ shape. Circuits whose depth-2 blocks are exponentially wide exhaust the bound before the depth iteration begins.

The accounting in one place

For a depth-$d$ circuit of size $s$ computing parity on $n$ variables: choose $p = n^{-1/(d-1)}$ up to constants. Each of the $d-1$ switching steps multiplies the failure probability by a factor that is small when $p w \ll 1$, and the accumulated width stays below $n^{1/(d-1)}$ as long as $s$ is below $2^{n^{1/(d-1)}}$ up to constants. The surviving variable count is about $n p = n^{1 - 1/(d-1)}$, which exceeds the width for large $n$, and the contradiction follows. Every quantity in that paragraph is a function of $d$, which is why the result is a hierarchy rather than a single separation, and why the same computation with $d = \log n$ yields nothing.