New arXiv paper refutes 3SUM and APSP hypotheses; Claude credited with subquadratic algorithm
burny_tech · x · 2026-10-06
A new arXiv paper by Josh Alman and Virginia Vassilevska Williams delivers the first polynomial improvements over textbook algorithms:
- 3SUM solved deterministically in O(n^1.9992) for polynomial-size integers, and APSP in O(n^2.9995) on directed graphs with polynomially bounded integer weights — refuting the 3SUM and APSP hypotheses.
- Via known reductions, this also refutes the real-valued versions of both hypotheses, the Exact Triangle hypothesis, the Zero-Weight k-Clique hypotheses, and three Online Matrix-Vector conjectures, with polynomial speedups for many other problems.
- The single engine behind all results is a new thin matrix product algorithm: computing up to N²/√D specified entries of an N×D by D×N product (D≤N^{1/18}) in O(N²/D^0.063) operations, built by adapting Coppersmith's rectangular matrix multiplication (from Schönhage's ten-multiplication identity).
Mira Murati amplified the result saying "Claude found a subquadratic 3SUM algorithm," sparking wide discussion of Claude's involvement.
Related event: Alman and Williams Break the n² and n³ Barriers for 3SUM and APSP(6 posts)→
More from Research
- O(n²) matrix multiplication is almost certainly false even if ω = 2, says basedjensen — basedjensen · 2026-10-06
- Cohere Labs Releases Tiny Aya, a Family of Small Models Covering 70+ Languages — Cohere_Labs · 2026-10-06
- Will LLMs wreck elegant math? O(n²) limits are already crumbling — teortaxesTex · 2026-10-06
- ETH's AME-2 legged locomotion paper accepted at TRO, training code open-sourced — ChongZzZhang · 2026-10-06
- 0.8B model beats 2B on ARC-Challenge (42.15%) via closed-form weight surgery with zero backprop — AdventurousTwo6445 · 2026-10-06
- MIT team's Science Task Taxonomy maps 232 subfields and 208,202 scientific tasks — JMateosGarcia · 2026-10-06