Superlinear Circuit Lower Bounds for Explicit Boolean Functions

Superlinear Circuit Lower Bounds for Explicit Boolean Functions

OpenAI's claim

OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 112; 2026-09-23), the asserted result is that one polynomial-time language eventually needs more than $2^{A\sqrt n}$ depth-three OR--AND--OR gates for every fixed $A$.

Mathematical statement of the claimed result

Manuscript 1.

The claim constructs one language $L\subseteq\{0,1\}^*$ decidable by a fixed deterministic Turing machine in polynomial time. For its length-$n$ Boolean function $f_n$ and minimum size $S_3(f_n)$ of circuits with three successive unbounded-fan-in layers OR--AND--OR, literal inputs and optional bottom constants, and free input negations, it asserts \[ \lim_{n\to\infty}\frac{\log_2S_3(f_n)}{\sqrt n}=\infty, \quad\text{equivalently}\quad \forall A>0\ \exists N_A\ \forall n\ge N_A:\ S_3(f_n)>2^{A\sqrt n}. \] The circuit family may be nonuniform, and there is no bound on bottom fan-in. The size counts every AND or OR gate, including gates in the bottom layer and the output gate.

Outline of the argument

For manuscript 1 (family 112; 2026-09-23), a random restriction expresses moderately wide CNFs as signed combinations of constant-width CNFs with controlled total coefficient mass. A fixed hard-slice language has low correlation with those tests, so no bounded number of middle gates can cover its positive inputs.

Formal verification

For manuscript 1 (family 112; 2026-09-23), OpenAI lists Lean statements for this assertion: one polynomial-time language eventually needs more than $2^{A\sqrt n}$ depth-three OR--AND--OR gates for every fixed $A$.

This coverage does not establish a formal proof of the complete problem as stated here.

The linked family Comparator checks are DepthThree.lean.

Their named declarations include OAI.DepthThreeLowerBound.exists_polynomial_time_language_depth_three_lower_bound.

This site has not executed the Lean code. Described statement coverage is not an independent proof check.

Status caveat

The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.

Sources

• OpenAI, Beyond the Square-Root Exponent for Depth-Three Boolean Circuits, 2026-09-23; citation key OAI:Beyond-the-Square-Root-Exponent-for-Depth-Three-Boolean-Circuits-September-23-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main.
• Family 112: Lean scope.
• Comparator DepthThree.json.
• Comparator DepthThree.lean.
• OpenAI catalogue entry.

Superlinear Circuit Lower Bounds for Explicit Boolean Functions

Definitions and mathematical statement

Let $\mathcal B_2$ be the set of all binary Boolean gates, with unrestricted circuit depth and fan-out. Denote by $C_{\mathcal B_2}(f_n)$ the minimum number of gates in a single-output circuit for $f_n$. Seek one uniformly polynomial-time computable family satisfying \[ \lim_{n\to\infty}\frac{C_{\mathcal B_2}(f_n)}{n}=\infty. \] Equivalently, every fixed linear bound is violated for all sufficiently large input lengths. A lower bound $cn-o(n)$ for one fixed $c$, no matter how large, is not superlinear in this sense.

Formulation and concept references: [S1].

Short English statement

Can an explicit polynomial-time Boolean function be proved to require more than every constant multiple of its input length in general circuit gates?

Research attempt

Current frontier.

Li--Yang prove a $3.1n-o(n)$ lower bound for explicit affine dispersers over the full binary basis. Their discussion of particular gate-elimination limitations is not a barrier against all lower-bound methods. A fixed constant cannot give the divergent ratio in this target. [S1] Restricted-model advances must remain separate: Rao's September 2026 manuscript gives exponential bounds for monotone matching circuits, not circuits with arbitrary binary gates. [E1]

Attack route.

Counting finds hard small truth tables but is too slow at the final input length. Padding restores polynomial-time uniformity while destroying the lower-bound ratio. We combine a slowly growing hard table with many disjoint input blocks and an XOR output. The missing step is a quantitative direct-sum estimate for unrestricted circuits, not the availability of hard tables at this small scale.

Attempt: construct a uniform hard-block family.

Allow free constants; this strengthens circuits and thus makes a lower bound in that model sufficient for the target. For $k\ge8$, set \[ s_k=\left\lfloor\frac{2^k}{16k}\right\rfloor. \] Topologically ordered circuits with $s_k$ gates have at most \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-37-3a-63-6f-75-6e-74} (k+s_k+2)\left[16(k+s_k+2)^2\right]^{s_k} \end{equation} descriptions. Padding with projection gates includes all smaller circuits. Since $k+s_k+2\le2^k$, the base-two logarithm is at most \[ k+\frac{2^k}{16k}(4+2k)<2^k. \] Thus fewer than the $2^{2^k}$ truth tables are represented. Let $h_k$ be the lexicographically first missing table. This definition is effective: enumerate descriptions, evaluate their tables, mark them and select the first unmarked table. The running time and space are $2^{O(2^k)}$, and $C_{\mathcal B_2}(h_k)>s_k$. It is not advice hiding an unspecified hard function.

For sufficiently large $n$, choose \[ k(n)=\lfloor\log_2\log_2n\rfloor, \qquad t(n)=\lfloor n/k(n)\rfloor, \] and on disjoint $k$-bit blocks define \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-37-3a-66-61-6d-69-6c-79} f_n(x)=\bigoplus_{i=1}^{t(n)}h_{k(n)}(x^{(i)}). \end{equation} Ignore the fewer than $k$ leftover bits and define the finitely many small lengths arbitrarily. Because $2^k\le\log_2n$, construction of $h_k$ takes $n^{O(1)}$ time with one fixed exponent; all subsequent table lookups and XOR operations are polynomial too. The logarithms defining $k$ are computed by integer bit lengths. Thus this is a genuinely uniform polynomial-time family meeting the explicitness requirement.

The precise amplification estimate that would suffice.

For these specific tables, suppose there is an absolute $\gamma>0$ such that \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-37-3a-44-53} C_{\mathcal B_2}\left(\bigoplus_{i=1}^{t}h_k(x^{(i)})\right) \ge\gamma t C_{\mathcal B_2}(h_k) \end{equation} uniformly at the required $k,t$. Then \[ \frac{C_{\mathcal B_2}(f_n)}n \ge c\frac{2^{k(n)}}{k(n)^2} \ge c'\frac{\log n}{(\log\log n)^2}\longrightarrow\infty. \] Floors change only constants at sufficiently large lengths. Unused bits cannot lower this bound: fixing them in any circuit gives a circuit of no greater size for the active-block function. This conclusion holds at every sufficiently large $n$, not only a sparse subsequence.

Even $\gamma_k$ tending to zero would suffice if $\gamma_k2^k/k^2\to\infty$. This quantitative relaxation is a possible attack target. Neither version of (30006747:DS) is proved here. Its implication for the original problem is a warning about its depth, not a reason to infer it from disjointness of variables.

What separation of blocks actually proves.

Consider the restricted architecture where each block enters its own disjoint subcircuit producing one bit $g_i(x^{(i)})$, and every later gate sees only these bits. If the output is (30006747:family), fix all blocks except $i$. The final function is unary in $g_i$ but must equal $h_k$ or $1-h_k$. Since $h_k$ is nonconstant for large $k$, this unary function is nonconstant; hence $g_i=h_k$ or $1-h_k$. Complementing costs at most one binary gate, so the $i$th subcircuit has size at least $C(h_k)-1$. Summing disjoint gate sets proves \[ C\ge t(C(h_k)-1) \] in this architecture. This verifies amplification when early cross-block mixing is prohibited, not in the catalogue's unrestricted model.

Stress test: why separate restrictions do not add.

In an unrestricted circuit, fixing all but one block gives an individual lower bound, but repeating this for each block gives a maximum, not their sum. A gate can survive many different restrictions. For example, on $t$ two-bit blocks first compute the XOR of all first bits and the XOR of all second bits, then XOR those two results. The last gate remains a genuinely binary XOR under every restriction leaving only one block. Charging it once per block counts the same gate $t$ times. The companion script checks this overlap directly; it is not merely counting gates that become removable unary identities after restriction.

Replacing disjoint blocks by repeated identical inputs is worse: $h_k(x)\oplus h_k(x)=0$. Disjoint variables avoid this cancellation but do not force disjoint internal computations. Bare padding $\widetilde f_n(x)=h_{k(n)}(x_1,\ldots,x_k)$ has a truth-table circuit of size $O(2^k)=O(\log n)$, so cannot be the desired family. A proof must control shared computation, not tacitly replace circuits by the block-separated architecture.

Outcome.

Outcome: Conditional reduction. A fully uniform polynomial-time candidate family has been constructed, and a specified disjoint-block direct-sum estimate would give an explicit divergent lower-bound ratio. Amplification is proved only for the restricted architecture; unrestricted mixing is the remaining gap. The counting mechanism is standard and no new general circuit lower bound is claimed. A solution of this weak superlinear problem would not alone imply $\mathsf P\ne\mathsf{NP}$: the constructed family is in $\mathsf P$ and could still have larger polynomial-size circuits.

Sources

• S1 3.1n - o(n) Circuit Lower Bounds for Explicit Functions, ECCC TR21-023,20February2021. https://eccc.weizmann.ac.il/report/2021/023/download/. Catalogue formulation source.
• E1 A. Rao, Monotone circuit lower bounds from spread matchings, author's manuscript, 3 September 2026, Theorem 1 and Corollary 2. https://homes.cs.washington.edu/~anuprao/pubs/matchinglowerbound.pdf.