{"id":"openai-math/Beyond-the-Square-Root-Exponent-for-Depth-Three-Boolean-Circuits","pdf":"https://github.com/openai/math/blob/main/preprints/Beyond-the-Square-Root-Exponent-for-Depth-Three-Boolean-Circuits-September-23-2026/main.pdf","url":"https://github.com/openai/math/tree/main/preprints/Beyond-the-Square-Root-Exponent-for-Depth-Three-Boolean-Circuits-September-23-2026","tags":["circuit-complexity","boolean-circuits","lower-bounds"],"score":0,"title":"Beyond the Square-Root Exponent for Depth-Three Boolean Circuits","domain":"Theoretical computer science","family":"112","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-23","reactions":{},"formalized":true,"family_title":"Beyond the square-root exponent for depth-three circuits"}