47.03.03 · theoretical-cs / advanced-complexity

AC0 and TC0: Parity Lower Bounds, Threshold Gates, and Circuit Separations

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §14.1-14.4 (Håstad's switching lemma with tight bounds, Razborov-Smolensky method for AC0[p] lower bounds, the ACC0 frontier)

Intuition Beginner

A committee of people is trying to reach a decision. They can only communicate in a fixed number of rounds. In each round, any person can gather information from any number of others, but the total number of people and rounds is limited. The question is: what decisions can this committee make?

A Boolean circuit is like this committee. It consists of gates connected by wires. AND gates check if all inputs are true. OR gates check if any input is true. NOT gates flip a single input. The depth of a circuit is the maximum number of gates on any path from input to output. The size is the total number of gates.

A constant-depth circuit has a fixed number of layers, no matter how many inputs there are. The gates in each layer can have any number of inputs (unbounded fan-in). This is the class AC0.

The parity function checks whether the number of 1s in the input is odd. It is one of the simplest Boolean functions you can imagine. Yet it turns out that AC0 circuits cannot compute parity efficiently. No matter how you arrange a constant number of layers of AND and OR gates, you need an enormous number of gates to get parity right on all inputs.

This is surprising. Parity is easy to compute with a simple loop: just flip a bit for every 1 you see. But a constant-depth circuit cannot "loop." It must compute its answer in a fixed number of rounds, and this restriction is devastating for parity.

The proof uses random restrictions. Imagine randomly freezing most of the inputs to fixed values. After the restriction, the circuit should simplify dramatically (many gates become constants). But parity does not simplify: after freezing inputs, the remaining function is still parity on the unfrozen inputs. This mismatch between how much the circuit simplifies and how much parity does not is the key to the lower bound.

Visual Beginner

An AC0 circuit computing a function on 6 inputs at depth 3:

          Output (AND)
         /     |     \
       OR     OR     AND
      /|\    /|\    / | \
     AND OR  AND OR AND OR
     ||| ||| ||| ||| ||| |||
     x1 x2 x3 x4 x5 x6

Parity on 6 inputs: 000001 $\to$ 1, 000011 $\to$ 0, 000111 $\to$ 1, etc.

Input	Parity	AC0 depth-2?
000000	0	Possible
000001	1	Possible
101010	0	Hard
111111	0	Hard
$n$ bits	$x_{1} \oplus \dots \oplus x_{n}$	Exponential size needed

The circuit hierarchy:

AC0  ⊂  TC0  ⊆  NC1  ⊆  L  ⊆  P

AC0:   AND, OR, NOT gates, constant depth, poly size
TC0:   MAJORITY gates, constant depth, poly size
NC1:   Bounded fan-in, O(log n) depth, poly size

Parity is in TC0 (using a majority gate to count 1s) and in NC1 (using a tree of XOR gates), but not in AC0.

Worked example Beginner

We sketch why parity is hard for depth-2 circuits.

A depth-2 AC0 circuit is either a DNF (an OR of ANDs) or a CNF (an AND of ORs). Consider a DNF for parity on $n$ bits. Each AND term tests for a specific pattern of inputs. To compute parity correctly, the DNF must accept exactly the strings with an odd number of 1s.

There are $2^{n - 1}$ strings with an odd number of 1s. A single AND term of width $k$ (using $k$ variables) covers $2^{n - k}$ strings. So to cover all $2^{n - 1}$ odd-parity strings, we need at least $2^{n - 1} / 2^{n - k} = 2^{k - 1}$ terms. But if $k$ is small, the terms do not discriminate enough, and some even-parity string gets accepted. If $k$ is large (close to $n$ ), we need many terms — the size becomes exponential.

For depth $d$ , the argument is more involved but follows the same principle: each additional layer of alternation helps, but not enough to bring the size down to polynomial for parity. The Håstad switching lemma quantifies this precisely.

Check your understanding Beginner

Formal definition Intermediate+

Definition (circuit classes).

$AC^{0}$ : languages decided by circuit families ${C_{n}}$ where each $C_{n}$ has $n$ inputs, polynomial size $∣ C_{n} ∣ \leq n^{c}$ , constant depth $O (1)$ , and unbounded fan-in AND, OR, NOT gates.
$TC^{0}$ : same as AC0 but with MAJORITY gates (output 1 iff $\sum x_{i} \geq ⌊ n /2 ⌋$ ) in addition to AND, OR, NOT.
$AC^{0} [p]$ : AC0 with MOD $_{p}$ gates (output 1 iff $\sum x_{i} \neq \equiv 0 (mod p)$ ).
$ACC^{0} = ⋃_{p} AC^{0} [p]$ .

Definition (parity function). $PAR_{n} (x_{1}, \dots, x_{n}) = x_{1} \oplus x_{2} \oplus \dots \oplus x_{n}$ .

Definition (random restriction). A $p$ -random restriction $ρ$ independently sets each variable $x_{i}$ to 0 with probability $(1 - p) /2$ , to 1 with probability $(1 - p) /2$ , and leaves it unset with probability $p$ . The restricted function $f ∣_{ρ}$ is $f$ with the fixed substitutions applied.

Theorem (Håstad's switching lemma). Let $f$ be a $k$ -DNF over $n$ variables and $ρ$ a $p$ -random restriction with $p = 1/ (10 k)$ . Then:

\Pr[\text{f|_\rho cannot be written as a k-CNF}] \le (5pk)^k.

Proof sketch. For each $k$ -DNF, the restriction $ρ$ sets most variables. The surviving variables are few. A case analysis shows that if the restriction does not simplify $f$ to a $k$ -CNF, there must be many "bad" terms, and the probability of this decays exponentially. The key lemma counts the number of restrictions that leave $f$ requiring more than $k$ terms of a CNF: this number is bounded by a combinatorial quantity that yields the desired probability bound. $□$

Theorem (parity lower bound). Any depth- $d$ AC0 circuit computing $PAR_{n}$ requires size $2^{Ω (n^{1/ (d - 1)})}$ .

Proof. Apply the switching lemma $d - 1$ times. At each step, a $k$ -DNF (or $k$ -CNF) is converted to a $k$ -CNF (or $k$ -DNF) via a random restriction. After $d - 1$ applications, the circuit has been simplified to a depth-1 function (a single AND or OR), but parity after $d - 1$ random restrictions still computes parity on $Ω (p^{d - 1} n)$ variables. If the circuit had size $S$ , the switching lemma succeeds at each step with high probability only if $S \cdot (5 p k)^{k}$ is small. Setting $p = n^{- 1/ (d - 1)}$ and optimising $k$ gives $S \geq 2^{Ω (n^{1/ (d - 1)})}$ . $□$

Counterexamples to common slips

"AC0 is the class of all polynomial-size circuits." No. AC0 requires constant depth. General polynomial-size circuits (with unbounded depth) can compute all of P.
"Parity is not computable at all." Parity is easily computable by a linear-size circuit of XOR gates. The lower bound says only that AC0 circuits (constant depth, AND/OR/NOT gates) need exponential size.
"The switching lemma applies to any circuit." The switching lemma applies to DNF/CNF formulas. For general circuits, it is applied layer by layer, peeling off one layer at a time using the DNF/CNF representation of each gate's function.

Key theorem with proof Intermediate+

Theorem (Furst-Saxe-Sipser / Ajtai parity lower bound). PARITY $\in /$ AC0. More precisely, any depth- $d$ circuit computing $PAR_{n}$ has size $2^{Ω (n^{1/ (d - 1)})}$ .

Proof. We use the random restriction method. Let $C$ be a depth- $d$ circuit of size $S$ computing parity. Choose $p = n^{- 1/ (d - 1)}$ and $k = \frac{1}{2} p^{- 1/ (d - 1)} lo g S = \frac{1}{2} n^{1/ (d - 1)^{2}} lo g S$ .

Apply a $p$ -random restriction $ρ_{1}$ to simplify the bottom two layers. Each bottom gate is a small DNF or CNF. By the switching lemma, with probability at least $1 - S \cdot (5 p k)^{k}$ , all bottom gates simplify to depth-1 functions, reducing the circuit depth by 1.

Repeat for $d - 2$ more restrictions $ρ_{2}, \dots, ρ_{d - 1}$ , each time reducing the depth by 1. After $d - 1$ restrictions, the circuit has depth 1: it is a single AND or OR of literals.

After all restrictions, the surviving variables number roughly $p^{d - 1} n = n \cdot n^{- (d - 1) / (d - 1)} = n^{0} = 1$ . But the switching lemma does not set all variables. A more careful analysis shows that $Ω (n^{1/ (d - 1)})$ variables survive with high probability.

The parity function restricted to $Ω (n^{1/ (d - 1)})$ surviving variables is still parity on those variables. But a depth-1 function (AND or OR) cannot compute parity on $m \geq 2$ variables. This is a contradiction unless $S \geq 2^{Ω (n^{1/ (d - 1)})}$ . $□$

Bridge. The parity lower bound builds toward the broader program of circuit complexity as a method for proving lower bounds against uniform classes: the central insight is that random restrictions exploit the locality of constant-depth circuits (each gate sees only bounded logical depth) while preserving the global sensitivity of parity. This appears again in 47.03.05 where the PCP theorem uses related probabilistic techniques (random testing and error amplification) to characterise NP by locally checkable proofs. The foundational reason the parity lower bound matters beyond AC0 is that it generalises to show $AC^{0} \neq = TC^{0}$ and $AC^{0} [p] \neq = AC^{0} [q]$ for distinct primes $p \neq = q$ , putting these together with the Razborov-Smolensky method gives a family of oracle separations relative to circuit classes, and this is exactly what makes circuit lower bounds the primary technical tool for attacking the P-vs-NP question from below.

Exercises Intermediate+

Exercise 6 (hard, symbolic).

Use the Razborov-Smolensky method to show that MOD3 (output 1 iff $\sum x_{i} \equiv 0 (mod 3)$ ) is not in AC0[2] (AC0 with MOD2 gates).

Answer

The key idea is that functions computable by AC0[2] circuits have low-degree polynomial representations over $F_{2}$ . By the Razborov-Smolensky lemma, any function $f$ computed by a depth- $d$ AC0[2] circuit of size $S$ can be approximated by a polynomial $P$ over $F_{2}$ of degree at most $(lo g S)^{O (d)}$ such that $Pr_{x} [f (x) \neq = P (x)] \leq ϵ$ . However, MOD3 requires any $F_{2}$ -polynomial approximating it to have degree $Ω (n)$ . This is because MOD3 partitions ${0, 1}^{n}$ into three equal parts (mod 3 classes), and any low-degree $F_{2}$ polynomial cannot distinguish three classes. The precise argument uses the fact that MOD3 is a symmetric function whose $F_{2}$ -polynomial degree is $Ω (n)$ (by a lemma of Smolensky using representation theory). Since $(lo g S)^{O (d)} = o (n)$ for any polynomial $S$ and constant $d$ , MOD3 cannot be in AC0[2].

Exercise 7 (hard, symbolic).

Prove that $PARITY \in TC^{0}$ by constructing a constant-depth TC0 circuit for parity.

Answer

Parity of $x_{1}, \dots, x_{n}$ equals 1 iff the number of 1s is odd, which is equivalent to: $MAJ (x_{1}, \dots, x_{n}, 0, \dots, 0) \neq = MAJ (x_{1}, \dots, x_{n}, 1, \dots, 1)$ where we append enough 0s or 1s to shift the threshold. More concretely: parity $= [\sum x_{i} mod 2 = 1]$ . Define the sum $S = \sum_{i = 1}^{n} x_{i}$ . Then $PAR = 1$ iff $S$ is odd. We can compute $S$ using a layer of threshold gates: $T_{k} (x) = [\sum x_{i} \geq k]$ for each $0 \leq k \leq n$ . Then $S = \sum_{k = 1}^{n} T_{k} (x) - T_{k + 1} (x)$ counts the sum (using TC0 addition on the threshold outputs). Parity is the least significant bit of this count, which is determined by a threshold comparison of the count modulo 2. The circuit has constant depth (a few layers of threshold gates) and polynomial size ( $O (n^{2})$ threshold gates).

Exercise 8 (hard, symbolic).

State and prove the reduction from an AC0 circuit to a low-degree polynomial approximation over $F_{2}$ (the first step of the Razborov-Smolensky method).

Answer

Lemma (Razborov-Smolensky approximation). For any AC0[2] circuit $C$ of depth $d$ and size $S$ on $n$ inputs, there exists a polynomial $P \in F_{2} [x_{1}, \dots, x_{n}]$ of degree at most $(lo g (S / ϵ))^{d}$ such that $Pr_{x} [C (x) \neq = P (x)] \leq ϵ$ .

Proof. By induction on depth. Base case depth 1: AND and OR gates compute symmetric functions with exact polynomial representations of degree $O (lo g S)$ . MOD2 gates compute $x_{1} \oplus \dots \oplus x_{k}$ , which has degree 1 over $F_{2}$ .

Inductive step: suppose each gate at depth $d - 1$ has a degree- $D$ polynomial approximation with error $ϵ / S$ . Composing these approximations through an AND gate $g = g_{1} \land g_{2} \land \dots \land g_{m}$ gives $P_{g} = P_{1} \cdot P_{2} \dots P_{m}$ , which has degree $m D$ . This may be large. Apply the probabilistic method: randomly sample a subset of the polynomials and take their product, using the fact that over $F_{2}$ , $x \land y = x y$ (multiplication). The degree reduction uses the fact that $P_{g}$ can be approximated by a degree- $D^{'}$ polynomial where $D^{'} = O (lo g (S / ϵ))^{d}$ . The OR gate $g = g_{1} \lor \dots \lor g_{m}$ is handled via De Morgan's laws. $□$

Lean formalization Intermediate+

Mathlib has no formalisation of Boolean circuits, circuit complexity classes (AC0, TC0, NC1), or the switching lemma. The foundational gap is the absence of a Circuit.Boolean typeclass with size and depth parameters, a formalisation of random restrictions as probability distributions on partial assignments, and the Håstad switching lemma as a proved theorem. The parity lower bound would require formalising the entire random-restriction argument, which is a significant undertaking. This unit ships without a lean_module.

Advanced results Master

Three frontiers in circuit complexity extend the parity lower bound.

Theorem 1 (Razborov-Smolensky). For distinct primes $p \neq = q$ , $MOD_{p} \in / AC^{0} [q]$ . Moreover, $AC^{0} [q] \neq = AC^{0} [p]$ ^{[Arora & Barak §14.4]}.

The proof uses the polynomial method over $F_{q}$ : every AC0[q] circuit of depth $d$ and size $S$ can be approximated by a degree- $(lo g S)^{O (d)}$ polynomial over $F_{q}$ . But MOD $_{p}$ requires degree $Ω (n^{1/2})$ over $F_{q}$ (since $F_{q}$ has characteristic $q \neq = p$ , the polynomial $x^{p - 1}$ cannot represent the residue classes mod $p$ ). This gives an exponential lower bound.

Theorem 2 (Williams' ACC0 lower bound). $NEXP \neq \subseteq ACC^{0}$ (Ryan Williams, 2011). This was the first superpolynomial lower bound against ACC0 for any explicit function. The proof uses the algorithmic method: a faster-than-brute-force SAT algorithm for ACC0 circuits would imply a collapse of NEXP, so the nonexistence of such an algorithm gives the lower bound.

Theorem 3 (frontier: TC0 vs NC1). It is open whether $TC^{0} = NC^{1}$ . Addition and multiplication of integers, division, and sorting are all known to be in TC0. If $TC^{0} = NC^{1}$ , then these operations can be performed in $O (lo g n)$ parallel time with bounded fan-in gates. The best known lower bound against TC0 is for the majority function in restricted models.

Synthesis. The parity lower bound is the foundational reason that circuit complexity provides concrete separations between computational models: the central insight is that constant-depth circuits with AND/OR/NOT gates have limited computational power due to their inability to maintain global sensitivity under random restrictions. This builds toward the Razborov-Smolensky theorem which extends the separation to AC0[p] versus AC0[q] for distinct primes, and appears again in 47.03.05 where the PCP theorem uses probabilistic techniques to show that NP proofs can be verified by reading only a constant number of bits — a depth-1 circuit-like restriction on proof access. The generalises from the specific parity function to a systematic understanding of which functions require depth versus size, and putting these together with the ACC0 frontier shows that circuit lower bounds are the most productive approach to the P-vs-NP question from below, even though the frontier remains at ACC0 and the full P-vs-NP separation via circuits is still open.

Full proof set Master

Proposition 1 (switching lemma bound). Let $f$ be a $k$ -DNF formula. Under a $p$ -random restriction with $p \leq 1/ (10 k)$ , the probability that $f ∣_{ρ}$ cannot be written as a $k$ -CNF is at most $(5 p k)^{k}$ .

Proof sketch. Let $f = T_{1} \lor T_{2} \lor \dots \lor T_{m}$ where each $T_{i}$ is a conjunction of at most $k$ literals. Consider a restriction $ρ$ that leaves $t$ variables unset. The restricted formula $f ∣_{ρ}$ is a $k$ -DNF on $t$ variables. By the dual version of the switching lemma, $f ∣_{ρ}$ fails to be a $k$ -CNF only if there exist $k + 1$ terms whose variables are all unset by $ρ$ and which together form a "bad" configuration. The number of such configurations is bounded by $(k + 1 t) \cdot k^{k + 1}$ , and each requires the restriction to unset all involved variables. Since the probability of unsetting a variable is $p$ , the total failure probability is at most $(k + 1 t) \cdot (p k)^{k + 1} \leq (tp k)^{k + 1} / (k + 1)! \leq (5 p k)^{k}$ for the appropriate choice of $p$ . $□$

Proposition 2 (parity requires exponential AC0 size). Any depth- $d$ AC0 circuit computing $PAR_{n}$ requires size $2^{Ω (n^{1/ (d - 1)})}$ .

Proof. Let $C$ be a depth- $d$ , size- $S$ circuit computing parity. Set $p = n^{- 1/ (d - 1)}$ and $k = c \cdot p^{- 1/ (d - 1)}$ for a small constant $c$ . Apply $d - 1$ successive random restrictions with parameter $p$ . After each restriction, apply the switching lemma to simplify the bottom layer. The probability that the switching lemma fails at any step is at most $S \cdot (d - 1) \cdot (5 p k)^{k}$ .

For this probability to be less than 1 (so the simplification succeeds for at least one restriction sequence), we need $S < (5 p k)^{- k}$ . Substituting $p = n^{- 1/ (d - 1)}$ and $k = c \cdot n^{1/ (d - 1)^{2}}$ :

$(5 p k)^{k} = (5 c n^{- 1/ (d - 1)} \cdot n^{1/ (d - 1)^{2}})^{c n^{1/ (d - 1)^{2}}} = (5 c n^{- (d - 2) / (d - 1)^{2}})^{c n^{1/ (d - 1)^{2}}}$

For this to be small, we need $5 c n^{- (d - 2) / (d - 1)^{2}} < 1$ , which holds for large $n$ . The size bound becomes $S \geq 2^{Ω (n^{1/ (d - 1)})}$ . $□$

Connections Master

47.03.02 — Boolean circuit fundamentals (size, depth, fan-in) provide the definitions on which AC0 and TC0 are built.
47.02.04 — The polynomial hierarchy is connected to circuit complexity via the Karp-Lipton theorem and the observation that AC0 lower bounds imply PH non-collapse.
47.03.05 — The PCP theorem uses techniques related to the switching lemma (random restrictions and error amplification) in its proof.
47.03.01 — BPP is contained in $Σ_{2}^{p}$ by the Sipser-Gacs-Lautemann theorem, which uses a construction related to circuit approximation.
47.05.03 — Miller-Rabin primality testing places primality in coRP $\subseteq$ BPP $\subseteq$ $Σ_{2}^{p}$ , and the circuit complexity of primality testing is a related open question.

Historical & philosophical context Master

The parity lower bound was proved independently by Merrick Furst, James Saxe, and Michael Sipser (1981) and Miklós Ajtai (1983). Both groups used the random restriction method, though Ajtai's proof was more general. Johan Håstad (1986) refined the switching lemma to give the optimal bound of $2^{Ω (n^{1/ (d - 1)})}$ , which matches an upper bound construction.

Alexander Razborov (1987) introduced the polynomial method for circuit lower bounds, proving that majority is not in AC0[2]. Roman Smolensky (1987) extended this to show that MOD $_{p}$ is not in AC0[q] for distinct primes $p \neq = q$ . The Razborov-Smolensky method remains the strongest general technique for AC0[p] lower bounds.

Ryan Williams' 2011 breakthrough showed that NEXP is not contained in ACC0, the first superpolynomial lower bound against any circuit class beyond AC0. His proof used the "algorithmic method": instead of proving lower bounds directly, he showed that faster circuit-analysis algorithms would imply collapses of complexity classes that are known not to collapse ^{[Arora & Barak §14.4]}.

The philosophical lesson of the parity lower bound is that computational limitations can be proved by probabilistic methods: random restrictions exploit the difference between the average-case behaviour of circuits and functions, even though the lower bound is worst-case. This bridges combinatorial analysis and complexity theory in a way that has proved remarkably productive.

Bibliography Master

@book{arora2009computational,
  author    = {Arora, Sanjeev and Barak, Boaz},
  title     = {Computational Complexity: A Modern Approach},
  publisher = {Cambridge University Press},
  year      = {2009},
}
@article{hastad1986computational,
  author  = {H{\aa}stad, Johan},
  title   = {Computational Limitations for Small-Depth Circuits},
  journal = {MIT Press},
  year    = {1986},
  note    = {PhD thesis, also published as monograph}
}
@inproceedings{furst1981parity,
  author    = {Furst, Merrick L. and Saxe, James B. and Sipser, Michael},
  title     = {Parity, Circuits, and the Polynomial-Time Hierarchy},
  booktitle = {Proceedings of the 22nd IEEE Symposium on Foundations of Computer Science},
  pages     = {260--270},
  year      = {1981},
}
@article{razborov1987lower,
  author  = {Razborov, Alexander A.},
  title   = {Lower Bounds on the Size of Constant-Depth Networks Over a Complete Basis with Logical Addition},
  journal = {Matematicheskie Zametki},
  volume  = {41},
  number  = {4},
  pages   = {598--607},
  year    = {1987},
}
@inproceedings{williams2011non,
  author    = {Williams, Ryan},
  title     = {Non-Uniform {ACC} Circuit Lower Bounds},
  booktitle = {Proceedings of the 26th IEEE Conference on Computational Complexity},
  pages     = {115--125},
  year      = {2011},
}

Prerequisites

47.03.02 pending

Tier anchors

beginner: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §14.1 (constant-depth circuits as a natural model of parallel computation, the parity function cannot be computed by small AC0 circuits)
intermediate: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §14.1-14.3 (Furst-Saxe-Sipser and Ajtai's parity lower bound via the switching lemma, Håstad's optimal $n^{Ω (l o g n)}$ lower bound for depth $d$ , TC0 and majority gates)
master: Arora & Barak 2009 Computational Complexity: A Modern Approach (Cambridge) §14.1-14.4 (Håstad's switching lemma with tight bounds, Razborov-Smolensky method for AC0[p] lower bounds, the ACC0 frontier)

References

Arora, S. & Barak, B. — Computational Complexity: A Modern Approach · Cambridge University Press (2009). Section 14.1 defines the circuit classes $AC^{0}$ (polynomial-size, constant-depth circuits of unbounded fan-in AND, OR, NOT gates), $TC^{0}$ (polynomial-size, constant-depth circuits of MAJORITY gates), and $NC^{1}$ (polynomial-size, $O (lo g n)$ -depth circuits of bounded fan-in gates). Section 14.2 proves the Furst-Saxe-Sipser/Ajtai theorem: the parity function $PAR (x_{1}, \dots, x_{n}) = x_{1} \oplus \dots \oplus x_{n}$ requires $AC^{0}$ circuits of size $2^{Ω (n^{1/ (d - 1)})}$ at depth $d$ . Section 14.3 presents Håstad's switching lemma: a $k$ -DNF over $n$ variables is approximated by a $k$ -CNF on a random restriction leaving each variable unset with probability $p = n^{- 1/ (d - 1)}$ with failure probability at most $O (α^{k})$ for a constant $α$ depending on $p$ . Section 14.4 discusses the Razborov-Smolensky theorem: $MOD_{p}$ is not in $AC^{0} [q]$ for distinct primes $p \neq = q$ .

Estimated time

beginner: 15m
intermediate: 40m
master: 75m