OpenAI proof dump shows first superlinear circuit lower bound, but progress stays slow
thomasahle · x · 2026-11-22
Thomasahle notes that OpenAI's proof dump achieved the first superlinear circuit lower bound, improving from 3.1n to n√(log n). He self-corrects that the bound applies to a problem in E^NP (not known open in P), and remarks that progress on circuit lower bounds remains slow—reaching n² and 2^n bounds is still far off.
Related event: OpenAI Proof Documents Show First Superlinear Circuit Lower Bound(2 posts)→
More from Research
- One photo, 8 VLAs, only 3 correct: ERQA embodied-reasoning benchmark questioned — giffmana · 2026-11-22
- Fleuret: treat AI as oracles, not explainers — human-comprehensible math will be negligible — francoisfleuret · 2026-11-22
- Vovk paper shows probabilistically nonrandom objects have vanishing universal measure — _onionesque · 2026-11-22
- AI generates a Riemann proof, AI generates the rebuttal—and it scores 100% AI — zetalyrae · 2026-11-22
- François Fleuret asks: is the gradient Japanese? It never refuses to give you a direction — francoisfleuret · 2026-11-22
- Hat Matrix Explained: How Much Leverage Does Each Data Point Have in Least Squares? — RobertTLange · 2026-11-22