Beyond the square-root exponent for depth-three circuits

Constructs a single language in deterministic polynomial time whose n-bit membership function requires 2^{\omega(\sqrt n)} total gates in unbounded-fan-in OR–AND–OR circuits, at every sufficiently large input length. This crosses the square-root-exponent threshold for explicit depth-three Boolean circuit lower bounds. (Lean)

Manuscript

Beyond the Square-Root Exponent for Depth-Three Boolean Circuits

September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:Beyond-the-Square-Root-Exponent-for-Depth-Three-Boolean-Circuits-September-23-2026}

We construct a language in deterministic polynomial time whose n-bit membership function requires 2^{\omega(\sqrt n)} gates in an unbounded-fan-in OR–AND–OR circuit. The bound holds at every sufficiently large input length and counts all gates, including the bottom layer.

Result 112 · Theoretical computer science. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Agora members.