Family 112Theoretical computer scienceLeanNot yet digested
Beyond the square-root exponent for depth-three circuits
Constructs a single language in deterministic polynomial time whose n-bit membership function requires 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.
Manuscripts in this family · 1
Beyond the Square-Root Exponent for Depth-Three Boolean Circuits
Sep 23, 2026·main.pdfLean
We construct a language in deterministic polynomial time whose n-bit membership function requires 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.