Håstad's Switching Lemma

Imagine a circuit made only of AND and OR gates, but you are allowed to stack them only a constant number of levels deep — no matter how many inputs you have. That is AC⁰: constant-depth, polynomial-size circuits with unbounded fan-in.

AC⁰ can do remarkable things. It can add numbers, compare them, sort a list, compute majority — all in just a handful of layers. For a long time it was tempting to think AC⁰ was essentially all-powerful.

Then came parity: the function that outputs 1 if an odd number of its $n$ inputs are 1, and 0 otherwise. Parity is the simplest function you can imagine that cares equally about every input. Yet no AC⁰ circuit can compute parity. The proof is Håstad's Switching Lemma (1987) — a single probabilistic argument that reveals why shallow circuits are fundamentally blind to parity.

The lemma is not just about parity. It is the master tool for proving lower bounds in circuit complexity: a way to show that certain problems are genuinely beyond the reach of shallow computation, no matter how many gates you throw at them.

The heart of the Switching Lemma is the random restriction: pick each variable independently, with probability $p$, to stay free; with probability $1-p$, fix it to a random bit. After the restriction, what remains should be a tiny formula.

The demo below shows a small DNF (OR of ANDs). Set the restriction probability $p$ and press Apply random restriction to randomly freeze some variables. Watch how many clauses survive, how many collapse to constants, and what the residual formula looks like.

<p class="hint">{{hint}}</p>
<div class="controls">
  <label>p = <span id="pval">0.30</span>
    <input type="range" id="pslider" min="0.05" max="1.0" step="0.05" value="0.30">
  </label>
  <button id="restrict" type="button">{{btn_restrict}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="formula-area">
  <div class="section-label">{{label_original}}</div>
  <div id="original-dnf" class="dnf-display"></div>
  <div id="result-area" class="hidden">
    <div class="section-label">{{label_after}}</div>
    <div id="restricted-dnf" class="dnf-display"></div>
    <div id="stats" class="stats"></div>
  </div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.controls { display: flex; flex-wrap: wrap; gap: .6rem; align-items: center; margin-bottom: .9rem; }
label { font-size: .9rem; display: flex; align-items: center; gap: .4rem; }
input[type=range] { width: 130px; }
button { font: 600 13px system-ui; padding: .42rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
#formula-area { margin-top: .4rem; }
.section-label { font-size: .78rem; font-weight: 700; text-transform: uppercase;
                 letter-spacing: .06em; color: #6b7a8d; margin: .6rem 0 .3rem; }
.dnf-display { display: flex; flex-wrap: wrap; gap: 6px; align-items: center; min-height: 2rem; }
.clause { display: flex; gap: 3px; align-items: center; background: #e8eef3;
          border: 1px solid #cdd9e3; border-radius: 8px; padding: 4px 8px;
          font: 600 13px ui-monospace, monospace; }
.lit { padding: 1px 4px; border-radius: 4px; background: #d0dae5; color: #1d3557; }
.lit.neg { background: #f0d5d8; color: #9b1c28; }
.lit.fixed-1 { background: #bbf0d0; color: #1a6636; }
.lit.fixed-0 { background: #e0e0e0; color: #999; text-decoration: line-through; }
.clause.true-clause { border-color: #1a6636; background: #e8f7ee; }
.clause.false-clause { border-color: #aaa; background: #f0f0f0; opacity: .5; }
.or-sep { color: #6b7a8d; font-weight: 700; font-size: 1rem; }
.stats { margin-top: .7rem; font-size: .88rem; line-height: 1.6; }
.stats b { color: #1d3557; }
.good { color: #1a6636; font-weight: 700; }
.bad  { color: #9b1c28; font-weight: 700; }
.hidden { display: none; }

// Code not found

Notice: when $p$ is small (say $p = 0.2$), most variables get fixed and the surviving formula shrinks dramatically. Håstad's lemma quantifies exactly how dramatically: with probability at least $1 - (5p)^s$, any width-$w$ DNF becomes computable by a decision tree of depth $s$ after a $p$-random restriction. That exponential shrinkage is what kills parity in AC⁰.

Status: proven impossible. Parity cannot be computed by any constant-depth, polynomial-size circuit. This was first shown by Miklós Ajtai (1983) and independently by Furst, Saxe, and Sipser (1984), but Håstad's 1987 thesis gave the optimal, quantitative version.

Here is the skeleton of the argument:

• What AC⁰ looks like. A depth-$d$ circuit of size $S$ can be written as a depth-$d$ formula. At depth 2 it is a DNF or CNF.
• The Switching Lemma. Fix any DNF with clause width $w$. Apply a $p$-random restriction ($p \approx 1/(10w)$). With probability at least $1 - (5pw)^s$, the restricted DNF becomes computable by a decision tree of depth $s$. A DNF "switches" to a small CNF (and vice versa), hence the name.
• Iterating the lemma. Apply restrictions layer by layer, depth by depth. Each application reduces the effective depth by 1 while the formula collapses faster than its size grows. After $d$ rounds, the entire circuit becomes a tiny decision tree.
• Parity resists. A decision tree for parity on $k$ free variables must have depth $k$ — it must read every variable. But after the restrictions, the number of free variables grows too slowly for parity to survive. Contradiction.
• The bound. Any depth-$d$ circuit for parity on $n$ bits needs size at least $2^{n^{1/d} / 2}$ — superpolynomial for any fixed $d$.

This is one of the first unconditional lower bounds in complexity theory: no assumption about P vs NP needed, just a clean probabilistic argument.

Håstad's Switching Lemma is far more than one result about parity:

• Circuit lower bounds. The lemma is the standard tool for proving that functions are not in AC⁰. Every subsequent lower bound in this class (majority, mod-$p$ for prime $p \neq 2$, inner product) descends from this technique.
• Pseudorandomness. A distribution that fools AC⁰ circuits — making them behave as if their inputs were random — can be built by exploiting the decision-tree structure the Switching Lemma exposes. This underlies constructions of pseudorandom generators for constant-depth circuits.
• Cryptography. The hardness of parity-based problems (related to Learning With Errors) and the weakness of certain hash functions in AC⁰ both trace back to the same structural insight.
• Complexity separations. The lemma separates AC⁰ from TC⁰ (threshold circuits) and was a template for later separations in the complexity landscape, including results around P vs NP.
• Teaching randomness in proofs. The Switching Lemma is a canonical example of the probabilistic method in combinatorics and complexity: instead of constructing a hard instance by hand, you show that a random construction works with high probability.

Understanding the Switching Lemma means understanding why randomization is one of the most powerful proof techniques in all of theoretical computer science.

The Switching Lemma is a masterclass in how mathematics handles impossibility. Instead of trying to show directly that no circuit works, Håstad used randomness as a proof tool: restrict variables at random, watch the formula collapse, and count what is left.

The result is definitive: parity is provably impossible for constant-depth polynomial-size circuits. It is one of the rare places in complexity theory where we have an unconditional answer — no open conjectures, no assumptions borrowed from elsewhere.

Every time you see a pseudorandom generator, a hardness result for shallow circuits, or a cryptographic argument about bit-by-bit independence, there is a good chance the Switching Lemma is quietly working in the background. It turned a simple observation about parity into one of the most influential tools in P vs NP research, and the echoes of Håstad's 1987 argument are still felt today.