Beyond the square-root exponent for depth-three circuits

What OpenAI claims

Constructs a single language in deterministic polynomial time whose n-bit membership function requires 2^ω(√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)

Paper

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

   23 September 2026 · Preprint, not peer reviewed · PDF

   OpenAI's abstract We construct a language in deterministic polynomial time whose n-bit membership function requires 2^ω(√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.

Status

Preprint. The paper has not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.