Depth-three circuits beyond the square root

OpenAI's theorem (2026) that one explicit polynomial-time language needs depth-three OR-AND-OR circuits with more than 2^(A sqrt n) gates for every constant A: a restriction bound for CNFs that does not depend on the number of clauses, a disjoint sparse partition by sunflowers, slices of a hash-and-polynomial language with limited independence, and a count of all gates.

Seven lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.

1. Depth-three circuits and the square-root barrier
2. A finite expansion of a restricted CNF
3. Path weights and backward counting
4. Sunflowers and a disjoint sparse partition
5. An explicit language
6. Hard slices
7. The lower bound

Theorems and assumptions · Reader and editable sources · Course record

Prerequisites

• Finite probability (expectation, independence, Markov's inequality) and the existence of finite fields (core course Abstract Algebra II); the course proves the other facts it uses.