Subquadratic 3SUM and Subcubic APSP

Alman and Vassilevska Williams present deterministic algorithms that break long-standing quadratic and cubic barriers: 3SUM on n integers of polynomial size in O(n^{1.9992}) time and All-Pairs Shortest Paths (APSP) on directed n-vertex graphs with polynomially bounded integer weights in O(n^{2.9995}) time. These results refute the 3SUM and APSP hardness hypotheses (including their real-valued versions) and, via standard reductions, also refute Exact Triangle and Zero-Weight k-Clique hypotheses and three rectangular Online Matrix-Vector conjectures of van den Brand, Nanongkai, and Saranurak, while yielding polynomial speedups for a range of related problems.

The technical core is a new algorithm for thin matrix products: given X (N×D) and Y (D×N) with D ≤ N^{1/18} and a set W of ≤ N^2/√D output positions, the algorithm computes the entries (XY)_{I,J} for (I,J)∈W in O(N^2/D^{0.063}) operations. The method adapts Coppersmith’s rectangular matrix multiplication framework, using Schönhage’s ten-multiplication identity, to perform only the operations needed for W. Interpreted as a graph algorithm, this yields truly subquadratic All-Edges Sparse Triangle detection in sparse lopsided tripartite graphs (two parts size n, one part n^{ε}), and known reductions from triangle detection give the improved 3SUM and APSP bounds; a data-structure variant answers single-entry queries for XY on demand.