Beyond the square-root exponent for depth-three circuits at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

A
D
V
E
R
T

I
S
E
M
E
N
T

Beyond the square-root exponent for depth-three circuits

at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

thinking... about 3 hours remaining

If this game doesn't work on your computer, go here for help. (Lean version available!)

expertly designed by an internal OpenAI model

Difficulty:	🧠🧠🧠🧠🧠	Ages:	13 - ∞
Skills:	algorithms, speed	Levels:	1
Category:	Theoretical computer science	Lean version:	YES! ✔
Rate this game! 4.9 out of 5 (1,241 votes)

>>> How to Play <<<

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.

>>> Level Select <<<

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

released 2026-09-23 | 1 theorem · 4 lemmas · 7 proofs · 8,574 words | PLAY LEVEL 1 » (pdf)

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.

More Theoretical computer science Games!
Exponential semidefinite complexity of perfect matching	The asymptotic Gotsman–Linial conjecture	A factor-two approximation for shortest common superstring	Exponential state costs for two-way automata
Fourier transforms below $n\log n$ HOT!	Polynomial mixing of graph switches with prescribed degrees	A counterexample to the quadratic sensitivity conjecture	The complexity of Weisfeiler–Leman refinement

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600