Anthropic's internal model found the first truly subquadratic 3SUM algorithm, preprint claims
AMBNNJ · reddit · 2026-10-06
A new preprint reports deterministic O(n^1.9992) 3SUM and O(n^2.9995) integer-weight APSP algorithms — the first polynomial improvements over the textbook n² and n³ bounds, refuting the 3SUM and APSP hypotheses.
- The key is a new thin matrix product algorithm; known reductions turn it into speedups for Exact Triangle, Zero-Weight k-Clique, Tree Edit Distance, and more
- SETH and Orthogonal Vectors are unaffected
- The paper states an Anthropic research model found the core algorithm on its own, with the main theorems formalized in Lean
If it holds up, this is a landmark case of AI making a genuine theoretical algorithms breakthrough rather than just scoring on benchmarks.
Related event: 3SUM and APSP Barriers Broken for the First Time, with Claude's Help(5 posts)→
More from AGI Musings
- What does human approval of an AI recommendation actually establish? Three tests for meaningful oversight — OkyEscritora · 2026-10-06
- After AI claimed a Millennium Problem proof, a mathematician argues it's math's renaissance, not its end — BachFrancis · 2026-10-06
- Kurzweil: AGI may arrive before 2029, and the 2030s could end death from aging — tomchapin · 2026-10-06
- AI Researcher Credit dispute sparks 'late-stage disempowerment' debate — BlackHC · 2026-10-06
- A Continuum View of Consciousness: From 12-Neuron Sea Creatures to Us — ctjlewis · 2026-10-06
- Consciousness Science Review: Where We Are and What If We Get There — coherence · 2026-10-06