AI-Discovered Algorithm Delivers First True Subquadratic 3SUM and Subcubic APSP
FrnkNlsn · x · 2026-10-06
An arXiv paper by Josh Alman and Virginia Vassilevska Williams gives the first polynomial improvements over textbook algorithms: deterministic 3SUM in O(n^1.9992) and APSP in O(n^2.9995), refuting the 3SUM and APSP hypotheses plus several related conjectures. The core is a new thin matrix product algorithm modifying Coppersmith-style rectangular multiplication. Per Carl Feynman's account, the algorithm was discovered by AI — someone at Anthropic stumbled on it while asking Claude to solve another problem, then funded two outside researchers to write the paper. Commenters call it a major advance in polynomial complexity.
Related event: Truly Subquadratic 3SUM and Subcubic APSP Break Decades-Old Barriers(7 posts)→
More from AGI Musings
- Goertzel's 2010 classic: 'The Singularity Institute's Scary Idea, and why I don't buy it' — burny_tech · 2026-10-06
- Ben Goertzel rebuts Yudkowsky: why the 'Everyone Dies' AGI doom argument is wrong — burny_tech · 2026-10-06
- Will Rinehart walks through AI extinction and catastrophe probabilities: less bleak than you think — WillRinehart · 2026-10-06
- Ben Goertzel's d-calculus: the math of goal preservation under AI self-improvement — burny_tech · 2026-10-06
- threepointone: Storytelling remains the ultimate alpha skill from campfire to livestream — threepointone · 2026-10-06
- NYT reviews Kevin Roose's 'The AGI Chronicles': how close is the race to superintelligence? — kevinroose · 2026-10-06