3SUM Solved in O(n^1.9992): Alman & Vassilevska Williams Refute the 3SUM and APSP Hypotheses
auto_grad_ · x · 2026-10-06
Josh Alman and Virginia Vassilevska Williams posted a new paper giving the first polynomial improvements over the textbook algorithms: 3SUM on n polynomial-size integers is solved deterministically in O(n^1.9992) time, and APSP on directed n-vertex graphs with polynomially bounded integer weights in O(n^2.9995) time. This refutes both the 3SUM and APSP hypotheses, long-standing cornerstones of fine-grained complexity theory.\n\nVia known reductions, the paper also refutes the real-valued 3SUM/APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight k-Clique hypotheses, and three rectangular hinted Online Matrix–Vector conjectures, while yielding polynomial speedups for many other problems. Everything follows from a single new algorithm for thin matrix products: for an N×D and a D×N integer matrix (D≤N^1/18), computing any N²/√D requested entries of the product takes only O(N²/D^0.063) operations—faster than computing those inner products one by one—built by modifying Coppersmith's rectangular matrix multiplication algorithm via a ten-multiplication identity of Schönhage.
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