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: Truly Subquadratic 3SUM and Subcubic APSP Break Decades-Old Barriers, Reportedly with Claude's Help(13 posts)→

Original post →

More from Research

Research channel →