Those ugly 0.99999984 complexity bounds aren't real — arbitrary 2^50 safety bounds, tighter results coming
aran_nayebi · x · 2026-10-08
Reacting to Craig Gidney's astonishment at AI-assisted complexity results (3SUM at O(n^1.9992), integer multiplication at O(n(lg n)^0.999...99984)), Konsti Wohlwend explains the ugly constants aren't real runtimes: authors use arbitrary safety bounds like 2^50 to simplify proofs, analogous to proving 1/x² > 0 only for x ≥ 99999. He expects the true bounds are far tighter, maybe 'beautiful' like O(n lg lg n), and that the AI papers' goal was just proving improvement is possible. Expect lots of tightening in coming months.
More from Research
- Scaling AI-guided experiments beats scaling biological data, researcher argues at ICML — anshulkundaje · 2026-10-08
- LLM Agents Form Factions by Model Family, Costing 30% More Rounds and 55% More Tokens — alex_verem · 2026-10-08
- AI Pinpoints Melon Yield Mutation in an Afternoon, Ranking #1 of 2,494 Candidates — GlennCameronjr · 2026-10-08
- AlphaFold-like tools solved problems no human could ever have tackled mathematically — JMateosGarcia · 2026-10-08
- NumanThabit aims to replace animal studies with sufficient physics simulation — MarwaEldiwiny · 2026-10-08
- Manuel Blum responds on matrix multiplication, citing his four 1964 conjectures — aran_nayebi · 2026-10-08