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.
More from AGI Musings
- Fields Medalist Bao Chau Ngo on AI proof of Riemann Hypothesis: treat AI output as data — Dr_Atoosa · 2026-11-22
- AI math pace outruns expert timelines: two Millennium Prize-level problems now reportedly solved — haider1 · 2026-11-22
- eigenrobot: In 2020 I'd have bet we'd prove the Riemann hypothesis before fixing obesity — eigenrobot · 2026-11-22
- AI researcher tszzl: a 'biblical flood' is coming to San Francisco, for obvious reasons — tszzl · 2026-11-22
- NYT Magazine asks: the internet broke our taste — will AI destroy it for good? — dreamwieber · 2026-11-22
- Tao expected the Riemann Hypothesis to fall by 2050 — it took AI only 35 days — SydSteyerhart · 2026-11-22