First truly subquadratic 3SUM algorithm refutes 3SUM and APSP hypotheses
ctjlewis · x · 2026-10-06
A new 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 breakthrough stems from a new thin matrix product algorithm modifying Coppersmith's rectangular matrix multiplication — a milestone in fine-grained complexity theory.
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