Computation Theory · Cluster
Circuit Complexity
Boolean circuits, lower bounds, and depth.
- 01 Circuit Families and the Non-Uniform Model of Computation How a Boolean circuit encodes one fixed input length, why decision problems need whole families of them, and what the missing uniformity assumption costs.
- 02 Gate Basis, Fan-In, and What Circuit Size Actually Counts Why the de Morgan basis, NAND alone, and unbounded fan-in bases give different gate counts, and how the conversions between them are constructed.
- 03 The Counting Argument for Circuit Size Lower Bounds Why almost every Boolean function on n bits needs about 2^n/n gates, how Lupanov matched that bound from above, and why the argument cannot name a single hard function.
- 04 Formula Size and the Tree-Shaped Restriction on Circuits What is lost when every gate may feed only one consumer, why parity needs a quadratic formula, and how circuit size converts to formula size at a quadratic cost.
- 05 The Switching Lemma and Why Parity Needs Depth to Compute How random restrictions collapse constant-depth circuits, why the lemma proves AC0 cannot compute parity, and where the argument runs out of room.
- 06 The Depth Hierarchy: NC, AC, and the Cost of Wide Gates How NCi and ACi interleave, why the hierarchy collapses if NC1 equals NC, and what the known separations at the bottom actually prove.
- 07 Monotone Circuits and the Approximation Method Why negations make lower bounds hard, how Razborov and Alon-Boppana proved exponential monotone size for clique, and what the method cannot say about matching.
- 08 Razborov-Smolensky and the Limits of Modulo Gates How low-degree polynomials over a finite field stand in for constant-depth circuits, and why AC0 with MOD-p gates cannot compute MOD-q for a different prime.
- 09 Size-Depth Tradeoffs and the Block-Respecting Model How restricting a circuit to communicate only between fixed blocks of inputs turns depth into a measurable resource, and what the resulting bounds say about parity.
- 10 The Natural Proofs Barrier and Why Circuit Lower Bounds Stall What makes a lower-bound argument natural, why such arguments cannot separate P from NP unless factoring is easy, and which techniques escape the barrier.