Beyond the square-root exponent for depth-three circuits

One fast-to-decide problem needs three-layer circuits bigger than any 2^(A√n) for large inputs.

1 paper September 23, 2026 Explained by AI

A three-layer circuit of OR and AND gates can answer any yes-or-no question about n input bits. Since 1989, proven size limits for explicit questions grew like 2 to the power of a constant times √n. This paper proves (Lean proof listed) that one problem a computer decides quickly beats every such constant. Its circuits eventually need more than 2 to the A√n gates, for any fixed A.

First step

1989

Johan Håstad, 2^Ω(√n) bound for parity

Significance

Major

If it holds, it moves explicit depth-three lower bounds past the constant-times-square-root scale.

Trust

Formal proof listed

Field

Theoretical computer science

1 paper

The explanation

Take two input bits, x1 and x2. Ask whether exactly one of them is 1. Here is a small circuit that answers. Two bottom gates are OR gates. One checks "x1 or x2". The other checks "not x1 or not x2". A middle AND gate demands that both checks pass. A top OR gate passes that answer out. Try all four inputs. The circuit says yes on 01 and 10, and no on 00 and 11. That is correct, and it used four gates.

This shape is called a depth-three OR–AND–OR circuit. It has exactly three layers of gates. Each gate may read as many wires as it likes. Flipping an input to "not" is free. Each bottom OR gate is a clause (an OR of inputs or their opposites). Each middle AND gate demands a list of clauses at once, which is called a CNF. So the whole circuit says yes when at least one middle CNF is satisfied. Every yes-or-no question about n bits can be answered this way. The cost is the total number of gates. The hard part is proving that some question needs many gates.

Lower bounds of this kind are old. In 1989, Johan Håstad showed that parity needs about 2 to the power c√n gates. Parity asks whether the number of 1s is odd, and c is some fixed constant. At n = 400 bits, √n is 20, and 2 to the 20 is about 1.05 million. In 1999, Paturi, Pudlák and Zane found parity's exact scale. It is about n to the 1/4 times 2 to the √n gates. At 400 bits, that is about 4.7 million, give or take a constant factor. A matching upper bound exists, so parity can never do better. In 2005, a related bound for another function reached an exponent of about 1.28√n. All of these stay at a constant times √n. A 2026 conference paper still lists going beyond that scale as open.

This paper proves the next step, and a Lean proof is listed. It builds one language: a fixed rule saying which strings of bits to accept. A single program decides it in polynomial time, meaning its running time grows like a fixed power of n. Pick any constant A, such as 3. Then for all large enough n, every such circuit for this language needs more than 2 to the A√n gatesSource 1. The program is fixed first, and A is chosen afterSource 2. So the gate exponent eventually beats every constant times √n.

The word "eventually" matters. How large n must be depends on A. For A = 3 at 400 bits, 2 to the 60 would be about 1.15 quintillion gates. The theorem does not claim that number at 400 bits. It also does not reach 2 to the power n^(1/2+ε) for a fixed ε above zero. That stronger question, asked in 1995, stays openSource 3. The result covers depth three onlySource 4. It counts every gate, including the bottom layer. That matters because any question can be written as one giant CNF.

The proof needs a question whose answers look unrelated to every fairly wide CNFSource 5. The obstacle is that a CNF may hold an enormous number of clauses. The paper's main tool removes that count. It fixes most input bits at random and leaves a few free. Each wide CNF then becomes a weighted mix of narrow CNFs. On average, the total weight stays at most two, however many clauses there wereSource 6.

The language itself takes data bits plus extra parameter bits. It hashes the data and plugs the result into a polynomialSource 7. The parameter bits choose the hash and the polynomial. Fixing them picks out one function of the data bits. For each target A, a random choice gives one with the needed property. The program never searches for that choiceSource 8. It just uses whatever bits it is handed.

The last step is counting. A circuit with S gates has at most S middle CNFsSource 9. Each one can say yes on only a tiny share of inputs. The chosen function says yes on at least a quarter of themSource 10. Too few gates cannot cover that many yes answers.

How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. A tool called Comparator matches it against a fixed reference statement. That statement covers one polynomial-time language and every constant A, with unrestricted fan-in and sharing. It does not assert a fixed exponent above one half, or any bound beyond depth three. No specialists have published a review yet.

What it doesn't show. This does not give a bound of 2 to the power n^(1/2+ε), or any bound for deeper circuits.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

A Lean proof of the main theorem is listed with a Comparator statement. Specialists have not published a review. The gain is past every constant times √n, not a larger fixed power of n.

Words used

Depth-three OR–AND–OR circuit: A circuit with a layer of OR gates, then AND gates, then one OR gate on top.
Clause: An OR of some input bits or their opposites.
CNF: An AND of clauses: it says yes only when every clause is satisfied.
Parity: The question of whether an input has an odd number of 1s.
Language: A fixed rule saying which bit strings are accepted, at every length.
Polynomial time: Running time that grows at most like a fixed power of the input length.
Lower bound: A proof that every circuit for a question needs at least some number of gates.
Comparator: A tool that checks a Lean proof proves exactly a fixed reference statement.

The original paper

Beyond the Square-Root Exponent for Depth-Three Boolean Circuits (PDF, opens in a new tab)
September 23, 2026 Formal proof listed

Lean notes

All quoted lines (10)

Equivalently, for every real $A>0$ , there is an integer $N_A$ such that $S_3(f_n)>2^{A\sqrt n}\qquad\text{for every }n\ge N_A.$
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
The word “one” matters: the language and its membership algorithm must be fixed before $A$ is chosen.
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
It is weaker than a lower bound $2^{n^{1/2+\varepsilon}}$ for a fixed $\varepsilon>0$ , the question raised in.
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
The depth remains three throughout.
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
The circuit argument needs a function whose sign has small correlation with every moderately wide CNF.
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
a constant … makes the expected total absolute coefficient mass at most two, independently of the number of clauses.
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
Membership evaluates a polynomial at a linear hash of the data, in the quotient ring specified by another input block.
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
The language's evaluator simply uses the supplied bits; it never has to find a hard slice or test irreducibility.
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
Finally, a circuit with $S$ total gates has at most $S$ middle CNFs, each with at most $S$ clauses, even when bottom gates are shared.
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text
The accepted set of the slice consequently has density $\Pr[g=1]=\frac{1+\E g}{2}\ge\frac14$ for every sufficiently large $n$ .
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits Back to text