Depth-three circuits beyond the square-root exponent

Source and verification

This article explains family 112 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Depth-three circuits and the size measure

An OR–AND–OR circuit has three successive layers. Bottom gates compute disjunctions of input literals, where a literal is a variable or its negation. Middle gates conjoin bottom outputs, producing conjunctive normal forms, or CNFs. The top gate takes their disjunction. Fan-in and sharing are unrestricted; input negations and constants are allowed freely.

Let $S_3(f)$ be the minimum total number of AND and OR gates in such an exact circuit for $f$. Every bottom gate and the output gate count. Counting only middle gates would be meaningless here: any Boolean function can be written as a single CNF, potentially using exponentially many clauses.

A language is polynomial-time decidable if one fixed algorithm decides membership on every input length in polynomial time. The circuit computing its length-$n$ membership function may vary arbitrarily with $n$; the lower bound does not impose circuit uniformity.

🏷️ One language beyond every square-root constant

Manuscript statement

There is one polynomial-time language with membership functions $f_n$ such that

$$\underset{n\to \infty }{\lim }\frac{{\log }_2{S}_3(f_n)}{\sqrt{n}}=\infty .$$

Equivalently, for every fixed $A>0$, all sufficiently large $n$ satisfy $S_3(f_n)>2^{A\sqrt{n}}$. The language and its polynomial-time evaluator are fixed before $A$ is chosen. (OpenAI, 2026)

This is stronger than improving the constant in a $2^{c\sqrt{n}}$ bound, but weaker than proving $2^{n^{1/2+\epsilon }}$ for a fixed positive $\epsilon$. An exponent such as $\sqrt{n}\log \log n$ illustrates the distinction. The result also concerns every sufficiently large length, rather than just an infinite subsequence, and only depth three.

🏷️ Correlation converts exact computation into a covering problem

Let $g$ be the sign of the target function, equal to $+1$ on accepted inputs and $-1$ otherwise. For a CNF indicator $H$, its correlation is $|\mathbb{E}[gH]|$ under uniform input.

Suppose $G$ is one middle CNF in an exact OR representation of the target. Wherever $G=1$, the target must accept, so $gG=G$. Thus

$$\mathrm{Pr}[G=1]=\mathbb{E}[gG].$$

If every middle CNF has small correlation, each covers few positive inputs. With at most $S$ middle gates, their union cannot cover a target of substantial positive density unless $S$ is large. Exactness is crucial: a middle gate that accepts negative inputs would no longer satisfy $gG=G$.

🏷️ Wide clauses and the total gate count

Assume a candidate circuit has $S$ total gates. Each middle CNF contains at most $S$ distinct bottom clauses, even if the bottom gates are shared. Remove every clause wider than $k$, making the resulting CNF $H$ weaker, so $G\le H$.

After removing repeated literals and tautological clauses, a width-$w$ clause fails on a uniform input with probability $2^{-w}$. A union bound therefore gives

$$\mathrm{Pr}[H\ne G]\le S{2}^{-k}.$$

If every width-$k$ CNF has correlation at most $\rho$, then

$$\begin{array}{rl}\mathrm{Pr}[G=1]& =\mathbb{E}[gG]\\ & \le |\mathbb{E}[gH]|+\mathrm{Pr}[H\ne G]\\ & \le \rho +S{2}^{-k}.\end{array}$$

Summing over all middle gates bounds the target’s acceptance density by

$$S\rho +S^2{2}^{-k}.$$

For a proposed $S\le 2^{A\sqrt{n}}$, the source chooses $k$ at the square-root scale with a sufficiently large constant and supplies a much smaller correlation $\rho$. The resulting bound contradicts the target slice’s near balance.

🏷️ Signed narrowing under random restrictions

A random restriction leaves each variable live with probability $p$ and independently fixes the others to fair bits. The manuscript’s main restriction lemma expresses the restricted width-$k$ CNF as a finite signed combination of width-$b$ CNFs. When $pk$ is bounded and $p\le 1/2$, a fixed $b$ suffices to make the expected sum of absolute coefficients at most two.

The bound is independent of the number of clauses. Its proof expands through simultaneous clause violations; counting paths backward cancels the number of available clauses against a reciprocal violation count. Keeping the narrow tests as CNFs permits a separate correlation construction to apply directly.

The signed coefficient mass and the quality of a restricted target may be dependent. Independence is unnecessary. On restrictions where every narrow test has correlation at most $\eta$, multiply $\eta$ by the coefficient mass. On the exceptional restrictions, bound the correlation of the original restricted CNF by one. Writing $M$ for the absolute coefficient mass, if the exceptional probability is $\zeta$, averaging gives at most

$$\eta \mathbb{E}M+\zeta \le 2\eta +\zeta .$$

Bounding the original indicator on the exceptional event avoids an unsupported assumption that large signed expansions occur independently of bad restrictions.

🏷️ Hard slices inside one easy language

The constructed language has a data block and parameter blocks. Its evaluator computes a polynomial at a linear hash of the data in a quotient ring specified by the input. Fixing the parameter bits selects a function of the data, called a slice.

For each desired lower-bound constant $A$, a probabilistic argument finds a hard slice. The evaluator never has to find that slice or test whether the supplied modulus is irreducible: it simply performs its prescribed arithmetic on the supplied bits. Thus the evaluator remains one fixed polynomial-time machine even though the lower-bound proof chooses different restrictions for different $A$.

The correlation argument first partitions constant-width CNFs into few sparse pieces of the same width. Their clause counts are linear in the number of live variables, leaving few enough tests for a simultaneous moment estimate. Linear hashing and polynomial evaluation provide the required limited independence. The constant-true CNF is among the tested functions, which also ensures that the hard slice is nearly balanced.

A circuit for the full language restricts to a circuit for every slice without increasing gate count. The hard-slice lower bound therefore transfers to the full membership function. The parameter accounting relates the data and parameter lengths to the original $n$; it is needed for the all-large-length theorem, not just for a family of separately constructed hard functions.

🏷️ Key steps and proof outlines

A finite mixture realizes reciprocal violation counts

The signed restriction lemma uses an elementary probabilistic identity to keep the output tests as narrow CNFs. Take an indexed family of clauses and $c$ distinct marker objects, uniformly permute them together, and conjoin the clauses appearing before the first marker. If an assignment violates exactly $w$ clauses, this conjunction accepts exactly when a marker precedes every violated clause. Symmetry gives acceptance probability

$$\frac{c}{c+w}.$$

Repeated clauses remain distinct indexed objects, so they are counted with their correct multiplicity. The identity also handles $w=0$ and clauses that become constant after restriction. It converts denominators arising in a signed expansion into convex mixtures of actual CNF indicators, rather than arbitrary rational functions. (OpenAI, 2026)

Counting a restriction expansion backward

A forward expansion path repeatedly selects a violated wide clause and fixes its newly encountered live coordinates. Let $D_h$ be the newly fixed coordinates at stage $h$; their number exceeds the target width $b$. Let $R_h$ be the still-live remainder. Reading the path backward restores $D_h$ and chooses a clause from the indexed set $V_{R_h}$ of eligible violated clauses.

For a live probability $p$, put $\alpha =2p/(1-p)$. The probability weight of the live set, combined with the factor undoing the newly fixed assignment cylinder, decomposes into products

$$\prod _h\frac{{\alpha }^{|D_h|}}{|V_{R_h}|}$$

times the terminal live-set probability. At each backward state, the denominator averages over the available clause indices, cancelling their count. Since each clause has width at most $k$, the remaining sum over newly restored subsets is bounded by

$$\sum _{j=b+1}^k\left(\genfrac{}{}{0ex}{}{k}{j}\right){\alpha }^j\le \sum _{j>b}\frac{(k\alpha {)}^j}{j!}.$$

When $pk$ is bounded and $p\le 1/2$, so is $k\alpha$. Choosing a sufficiently large fixed $b$ makes this exponential-series tail less than a chosen constant below one. Summing path lengths as a geometric series bounds the expected absolute coefficient mass, independently of the original number of clauses. This cancellation is the key reason the restriction lemma tolerates very large CNFs.

Correlation losses compose without an independence assumption

For a good restriction, every resulting width-$b$ CNF has target correlation at most $\eta$. A signed combination with absolute mass $M$ then has correlation at most $\eta M$. On bad restrictions, use the original restricted indicator’s correlation bound of one. If bad restrictions have probability $\zeta$,

$$|\mathbb{E}[gH]|\le \eta \mathbb{E}M+\zeta \le 2\eta +\zeta .$$

The coefficient mass may be highly correlated with restriction quality; the displayed inequality never factors these quantities. The sparse-CNF decomposition and moment argument provide the simultaneous narrow-test bound needed on good restrictions. Testing the constant function at the same time also forces near balance of the hard slice.

From correlations to all-gate lower bounds

For a hypothetical circuit with $S\le 2^{A\sqrt{n}}$ gates, each middle CNF covers positive inputs only. Truncating clauses above width $k$ costs at most $S{2}^{-k}$ per middle gate. Hence its positive density is at most $\rho +S{2}^{-k}$, and the whole circuit covers at most $S\rho +S^2{2}^{-k}$. Choose $k>2A\sqrt{n}$ with a further fixed margin and make $\rho$ smaller than $2^{-A\sqrt{n}}$ by the hard-slice construction. The covering bound then contradicts near balance.

The parameter bits specifying a hard slice are fixed only in the lower-bound proof. The language evaluator accepts arbitrary parameter bits and executes one fixed polynomial-time arithmetic procedure. Restricting a circuit to those bits does not increase its gate count, so hardness of the selected slice implies hardness of the full length-$n$ function. The source’s length accounting makes this argument work at every sufficiently large length for each fixed $A$.

See Also

• Approximation hardness uses Fourier and local-decoding arguments for reductions; this family instead proves a lower bound in a fixed circuit model.
• Fourier degree studies another restricted measure of Boolean complexity and explains why different complexity parameters need separate conclusions.

🏷️ Manuscripts and verification scope

• Beyond the Square-Root Exponent for Depth-Three Boolean Circuits — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The comparator selects one polynomial-time language before the lower-bound constant, counts all gates, allows arbitrary fan-in and sharing, and asserts the lower bound at every sufficiently large input length. It does not assert a fixed positive power improvement in the exponent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Beyond the Square-Root Exponent for Depth-Three Boolean Circuits.