Boolean Circuits: Inside OpenAI’s Proof of a Stronger Depth-Three Lower Bound

A three-layer logic circuit can read every input bit at once and reuse intermediate results freely. OpenAI’s new construction still forces it beyond every constant-times-square-root exponential size bound. The September 23, 2026 paper presents one efficiently computable language whose depth-three Boolean circuits require $2^{\omega(\sqrt n)}$ gates at every sufficiently large input length.

That is the OpenAI Boolean circuit complexity proof’s central claim. It strengthens a specific shallow-circuit lower bound, without resolving P versus NP or demonstrating faster AI software. Released in OpenAI’s October mathematics announcement, it also illustrates why research proofs and benchmark scores are different evidence. Here, the achievement is ruling out every small representation allowed by a precisely defined model.

1. What OpenAI Proved About Depth-Three Boolean Circuits

Theorem 1.1 of the research manuscript fixes a language $L$, one deterministic Turing machine, and positive integers $C,a$. That machine decides membership within $C(n+1)^a$ steps. Let $f_n$ be membership on $n$-bit inputs and $S_3(f_n)$ the minimum total AND/OR gate count. Then, for every fixed $A>0$:

The threshold $N_A$ may depend on $A$. The language, machine, and runtime constants cannot. Circuits may change arbitrarily with input length. The bound holds eventually at all lengths, rather than along a convenient infinite subsequence. This rules out changing the language whenever someone asks for a larger lower-bound constant. Choose a million for $A$, and the same evaluator still works. What changes is how far along the input-length sequence the guarantee begins. The theorem supplies no practical crossover length.

1.1. Boolean Circuits: The Key Facts

2. The Original Boolean Circuit Lower-Bound Problem

Boolean circuit complexity asks how many logic gates are necessary to represent a function. Counting arguments show that most truth tables need enormous circuits. The difficult task is proving such hardness for an explicitly specified, efficiently computable function.

There is no contradiction in putting the language in polynomial time. A Turing machine can carry out many sequential stages. The theorem’s circuit must squeeze its computation into three successive layers. Polynomial-time algorithms have polynomial-size general circuits, but those circuits need not have depth three.

This is a representation bottleneck. Our permanent versus determinant explainer examines another representation problem, in algebraic complexity. Likewise, discrete Fourier transform complexity depends on permitted operations. Neither result transfers automatically between models. Here the central question is whether a shallow classical circuit can reproduce every output exactly, irrespective of how cleverly its gates are wired. Circuit nonuniformity makes that challenge stronger: there is no requirement for a single efficient program to generate the circuit at each length. The lower bound defeats even separately chosen wiring diagrams. The construction is efficient on the algorithm side while allowing this freedom on the circuit side.

3. Why Previous Parity Lower Bounds Stopped at the Square-Root Exponent

Parity returns whether an input contains an odd number of ones. Håstad’s random-restriction and switching method established depth-three circuit lower bounds at the $2^{\Omega(\sqrt n)}$ scale. Håstad, Jukna, and Pudlák later improved constants through a top-down approach.

Paturi, Pudlák, and Zane obtained the sharp parity lower bound $\Omega(n^{1/4}2^{\sqrt n})$, matching its upper bound within a constant factor. Thus parity itself cannot exceed every $2^{A\sqrt n}$. A larger constant in an existing proof cannot overcome a matching construction.

The new paper therefore changes the hard function. Its qualitative gain is an exponent whose ratio to $\sqrt n$ diverges. As with exponential improvements in Subset Sum, changing an asymptotic rate differs from shaving a polynomial factor. And, as our quadratic sensitivity explainer illustrates, the precise growth comparison determines what a Boolean-function separation actually says.

4. Understanding the OR–AND–OR Circuit Model

Read the layers from inputs upward. Bottom OR gates form clauses from literals, meaning variables or their negations. Middle AND gates join clauses into conjunctive normal forms, or CNFs. The output OR accepts whenever any middle CNF accepts. These depth 3 circuits allow unrestricted finite fan-in and fan-out, including shared bottom gates. Input negations and constants are free.

For a worked example, define clauses $C_1=x_1\lor\neg x_2$, $C_2=x_2\lor x_3$, and $C_3=\neg x_1\lor x_3$. Use two middle gates for $C_1\land C_2$ and $C_1\land C_3$, then OR their outputs. This implementation has three bottom gates, two middle gates, and one output gate: six total. The shared clause counts once. Input $(1,1,0)$ accepts through the first middle gate.

This is an implementation count, not a claim of minimality. Counting only middle gates would be misleading: any Boolean function has a potentially enormous single-CNF representation. Our random 3-SAT guide explains the same clause vocabulary, while quantum circuit lower bounds concern a different gate model.

5. The Central Proof Idea: Low Correlation Forces Large Circuits

Encode the hard function as a sign $g$: positive one on accepted inputs, negative one otherwise. A CNF indicator $H$ instead takes values zero and one. The relevant correlation is $|\mathbb E[gH]|$, with expectation over uniformly random inputs. It measures the imbalance between accepted and rejected points inside the CNF’s satisfying set. This is an unnormalized correlation. A tiny CNF satisfying set automatically has small correlation, even if every point in it is positive. The argument deliberately exploits that fact: an exact middle gate with low correlation must cover only a tiny fraction of the whole cube.

If $H$ feeds an exact OR representation, it cannot accept a negative point. Consequently $gH=H$, and small correlation forces $\mathbb E H$, its acceptance density, to be small.

Now imagine covering a substantial positive set with such CNFs. Each covers very little, so many are necessary. This resembles covering a floor with tiny tiles, except overlapping tiles still count against the budget. The proof engineers a slice with positive density and uniformly low CNF correlation, then handles wide clauses separately.

6. Constructing OpenAI’s Polynomial-Time Hard Language

Definition 5.1 starts with $d=\lfloor n/5\rfloor$ data bits, rejects when $d<64$, and sets $r=\lceil d^{2/3}\rceil$. Let $t$ be the largest nonnegative even integer satisfying $t^6\le d$. The input then supplies $d+r-1$ hash bits, $r$ modulus bits, and $t$ coefficient blocks of $r$ bits each.

The modulus bits encode the monic polynomial $P(Z)=Z^r+\sum_{i=0}^{r-1}p_iZ^i$ over $\mathbb F_2$, arithmetic modulo two. Computation occurs in the quotient ring $R_P=\mathbb F_2[Z]/(P)$, where polynomials are reduced to degree below $r$.

Hash coordinate $h_i(x)=\sum_{s=1}^{d}u_{i+s-1}x_s\pmod 2$ defines $h(x)=\sum_{i=1}^{r}h_i(x)Z^{i-1}$. Its matrix is Hankel, constant along anti-diagonals, or Toeplitz after reversing data coordinates. With supplied coefficients $\beta_j$, acceptance means:

Here $\lambda$ extracts the constant coefficient of the reduced representative. Unused bits are ignored. A defensive rejection checks block availability, although the blocks fit whenever $d\ge64$.

Monicity makes reduction well-defined even for reducible moduli. Direct hashing and Horner evaluation use $O(rd+tr^2)$ bit-array operations, with polynomial Turing-machine overhead. The evaluator neither tests irreducibility nor searches for hard parameters. Fixing those supplied parameters selects a data function called a slice. As a toy illustration of quotient arithmetic, reducing modulo $Z^2+Z+1$ replaces $Z^2$ with $Z+1$, since addition and subtraction coincide modulo two. The actual construction uses much larger degrees. The example simply shows why multiplication can return to a fixed-length coefficient array.

7. Random Restrictions and OpenAI’s Signed CNF Restriction Lemma

A random restriction leaves each data variable live with probability $p$, independently, and fixes all others to independent uniform bits. Ordinary simplification need not make every clause narrow when a CNF contains arbitrarily many clauses.

Lemma 3.1 instead represents a restricted width-$k$ CNF as a finite signed combination of width-$b$ CNFs. Signed means coefficients may be negative, not that logical gates acquire negative inputs. Its controlling parameter is:

The expected total absolute coefficient mass is bounded by $1/(1-\theta)$. With bounded $pk$ and $p\le1/2$, choosing a sufficiently large constant $b$ makes this at most two, independently of clause count. Width counts distinct variables in an individual normalized clause. For example, fixing $x_1=0$ in $x_1\lor x_2\lor\neg x_3$ leaves a two-variable clause. Fixing $x_1=1$ makes that clause true, so it disappears from the conjunction. The signed expansion addresses clauses that remain too wide after this elementary simplification.

The expansion follows paths of successive clause violations. Counting backwards pairs each possible violated-clause choice with a reciprocal violation count, cancelling dependence on how many clauses are eligible. Classical switching-lemma estimates also avoid a clause-count parameter, but change the normal form. Here the tests remain CNFs. That is the useful distinction in this random-restrictions argument, not a claim that earlier methods ignored formula size.

8. Sunflower Sparsification and Disjoint CNF Partitions

Narrow CNFs still form too large a test family. Lemma 4.1 makes them sparse: for fixed width $b$ and any $\eta>0$, a CNF on $m$ variables partitions into at most $2^{\eta m}$ CNF indicators. Each retains width at most $b$ and has at most $Mm$ clauses, where $M$ depends only on $b,\eta$.

A sunflower is a family of sets sharing a core, with pairwise disjoint petals outside it. Applied to clauses, branching separates assignments satisfying the core from assignments falsifying it and satisfying the petals. Explicitly requiring the core to be false on the second branch keeps the pieces disjoint.

The proof tracks clause-insertion budgets and bounds branch histories through binary entropy. This controls both leaf count and clause count. Disjointness makes the original indicator exactly the sum of its pieces, avoiding inclusion–exclusion. These are exact identities between indicators, not approximations of satisfying sets. The later error terms come from exceptional restrictions and deleted wide clauses. Keeping these sources separate makes the final probability budget easier to audit. Sparsification also appears in the background of exponential-time hypotheses and SAT, though the present goal is controlling correlation tests. For fixed width, only polynomially many different clauses exist on $m$ variables. Limiting each piece to linearly many clauses therefore leaves at most $2^{O(m\log m)}$ sparse tests. This finite counting bound is what makes a simultaneous probability estimate feasible.

9. How Universal Hashing and Polynomial Interpolation Produce Hard Slices

For the hardness argument, select an irreducible modulus, making $R_P$ a field of $2^r$ elements. A random hash sends each nonzero difference uniformly into that field. On an $m$-dimensional restricted cube, a union bound makes hash-collision probability at most $2^{m-r}$. This uses linear-hash universality, not strong pairwise independence of hash outputs.

When the hash is injective, polynomial interpolation makes evaluations at any $t$ distinct cube points independent and uniform. Applying $\lambda$ produces unbiased, $t$-wise independent signs. For a fixed sparse indicator $J$, set $Y=\sum_zg(z)J(z)$. Expanding the even moment gives $\mathbb E Y^t\le t^t2^{mt/2}$: tuples containing a point just once contribute zero.

Markov’s inequality and a union bound control every sparse test simultaneously. Sparsification with $\eta=1/8$ then yields correlation at most $2^{-m/8}$ for every width-$b$ CNF.

Proposition 5.3 chooses $p=B/\sqrt d$, giving mean live dimension $m_0=B\sqrt d$. A parameter setting exists whose restriction-failure probability is at most $4\cdot2^{-m_0/16}$, including dimension tails outside $[m_0/2,2m_0]$. Averaging proves existence. The evaluator simply reads its parameters, so it need not discover this hard setting. The parameter scales serve separate purposes. Degree $r$, growing like $d^{2/3}$, eventually exceeds the live dimension, which grows like $\sqrt d$, suppressing collisions. Independence order $t$, growing like $d^{1/6}$, eventually dominates the logarithmic cost of enumerating sparse tests. These comparisons hold with the proof constants fixed.

10. Completing the Proof: From CNF Correlation to the Gate Lower Bound

Fix a proposed exponent constant $A>0$. Choose $s=3A$, $B=64(s+1)$, $p=B/\sqrt d$, and $k=\lceil3(s+1)\sqrt d\rceil$. Next choose constant width $b$ large enough for $\theta\le1/2$, then take sufficiently large inputs. Combining the restriction lemma with Proposition 5.3 gives, for every width-$k$ CNF:

No independence between coefficient mass and good restrictions is assumed. The constant-true CNF also qualifies, so the slice is nearly balanced and eventually accepts at least one quarter of inputs.

Suppose an exact circuit has $S\le2^{A\sqrt n}$ total gates. Fixing parameter bits cannot increase size. Each of its at most $S$ middle CNFs has at most $S$ clauses. Deleting clauses wider than $k$ enlarges each satisfying set by probability at most $S2^{-k}$, since each deleted clause fails with probability at most $2^{-k}$. This explains the squared size term: one factor budgets clauses per middle gate, and another budgets middle gates. Sharing bottom gates does not invalidate either upper bound. Counting all gates ensures both budgets remain available even when bottom fan-in is unrestricted.

Correlation bounds the enlarged CNF, with that deletion error added back. Summing across middle gates yields:

Since $n\le9d$ eventually, the right side is at most $6\cdot2^{-(3s+4)\sqrt d}+2^{-(s+3)\sqrt d}$, which tends to zero. That contradicts acceptance density of at least one quarter. Arbitrary $A$ gives the claimed Boolean circuit lower bounds.

11. What the OpenAI Proof Establishes, What Remains Open, and Lean Verification

The improvement concerns exact depth-three representations with arbitrary bottom width. It establishes neither unrestricted-circuit hardness nor P versus NP. A bound $2^{n^{1/2+\varepsilon}}$ for fixed $\varepsilon>0$ remains beyond this theorem. Developers should infer no measured SAT, chip-design, or neural-network speedup. As with quantum query complexity, the resource being counted matters.

OpenAI’s published Lean scope covers the fixed polynomial-time language and eventual total-gate bound. The formalization catalogue points to a proof entry combining those results. This article has not rebuilt that Lean development. Formal checking also differs from independent peer review, a distinction explored in our Fermat formalization analysis.

For researchers checking the result, start with the formal theorem’s order of quantifiers and its circuit definition. Then follow the separate evaluator and lower-bound dependencies. Merely finding a theorem statement is insufficient: a comparator challenge can intentionally contain an unproved placeholder, while the implementation proof lives elsewhere. The catalogue distinguishes those roles. For developers, the reusable insight is methodological: fixing parameter bits can expose a hard subfunction without making parameter search part of the computation. That separation is central to why probabilistic existence and a deterministic evaluator coexist here.

The useful lesson for AI readers is to inspect the quantifiers, permitted resources, and verification scope together. For Boolean circuits, the square-root constant barrier is precisely the advance to understand. Keep reading Binary Verse AI for research explainers that connect the theorem to its proof and preserve the limits of what it establishes.