Parity Function

The parity function is the Boolean function that outputs 1 if and only if the number of 1s in its binary input is odd. Formally, for an n-bit input x = (x₁, x₂, ..., xₙ), the parity function is defined as:

⊕(x) = x₁ ⊕ x₂ ⊕ ... ⊕ xₙ

where ⊕ denotes the XOR operation. Parity is one of the simplest symmetric Boolean functions — its output depends only on the sum of the inputs, not on their arrangement — yet it occupies a position of outsized importance in computational complexity theory. The function is computationally trivial: it can be computed by a linear-size circuit of XOR gates, by a Turing machine in linear time, and by a finite automaton with a single bit of memory. Its significance lies not in its intrinsic difficulty but in what its limitations reveal about restricted models of computation.

The AC⁰ Lower Bound

The canonical result in circuit complexity is that parity is not in AC⁰: no constant-depth, polynomial-size circuit with unbounded-fan-in AND, OR, and NOT gates can compute parity. This was proved independently by Furst, Saxe, and Sipser (1984) and Ajtai (1983), and it remains one of the most influential lower bounds in theoretical computer science.

The proof techniques are themselves landmarks:

• Random restrictions: Furst-Saxe-Sipser showed that applying a random restriction (setting most input variables to random constants) to an AC⁰ circuit yields a function that depends on only a small number of variables, whereas parity restricted to any subset of its variables remains parity on that subset — a function that depends on all of them.

• Polynomial approximation: Razborov and later Smolensky showed that AC⁰ circuits can be approximated by low-degree polynomials over finite fields, but parity cannot be so approximated. Smolensky's method extended the lower bound to MOD_p functions (counting modulo a prime) against circuits with MOD_q gates for q ≠ p.

The parity lower bound was the first superpolynomial lower bound for a natural problem in a natural circuit class. It established that depth is a genuine computational resource: there exist functions computable with logarithmic depth that cannot be computed with constant depth, regardless of how much the width is increased. This validated the central hypothesis of circuit complexity: that computational resources (size, depth, gate types) can be separated, and that these separations reveal something fundamental about the structure of computation.

Parity and Neural Computation

The parity function occupies a curious position in the history of neural networks. In 1969, Minsky and Papert proved that a single-layer perceptron cannot compute parity: no linear threshold function can separate the odd-parity inputs from the even-parity inputs in {0,1}ⁿ. This result was one of the primary motivations for the introduction of hidden layers in neural architectures — the recognition that local computation (a single threshold gate) cannot capture global structure (the parity of the entire input vector).

The Minsky-Papert theorem on parity is structurally identical to the AC⁰ lower bound, though the proof techniques differ. Both results say: local operations cannot detect global properties. A single perceptron performs a local weighted sum; a constant-depth circuit performs a local composition of AND/OR operations. Neither can accumulate information across the entire input in the way that parity requires. The necessity of depth — whether in circuits or in neural networks — emerges from the same systems principle: computation that integrates information over a global domain requires a corresponding depth of processing.

Modern deep learning has empirically confirmed what complexity theory proved theoretically: depth matters. The parity function is now used as a canonical test case for mechanistic interpretability research, where it serves as a minimal example of a task that requires multi-layer computation. Studies of how transformers learn parity have revealed that networks develop specialized parity