Subquadratic 3SUM and Subcubic APSP

A breakthrough gives the first polynomial improvements over the textbook runtimes for 3SUM and All-Pairs Shortest Paths: deterministically solving 3SUM on n integers of polynomial size in O(n^{1.9992}) time and APSP on directed n-vertex graphs with polynomially bounded integer weights in O(n^{2.9995}) time. These bounds refute the standard 3SUM and APSP hardness hypotheses and, via known reductions, also refute the real-valued versions of those hypotheses plus Exact Triangle, Zero-Weight k-Clique, and several rectangular hinted online matrix-vector conjectures, 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 at most N^2/√D target positions, it computes the entries (XY)_{I,J} for (I,J)∈W in O(N^2 / D^{0.063}) operations, which is polynomially below the cost of forming all of XY or computing those inner products one-by-one. The method modifies Coppersmith’s rectangular matrix multiplication machinery, leveraging Schönhage’s ten-multiplication identity to perform only the necessary operations. Interpreted graph-theoretically, this solves All-Edges Sparse Triangle in truly subquadratic time on lopsided tripartite graphs (two parts of size n and one of size n^ε for ε ≤ 1/18), and the authors also give a data-structure variant that answers single-entry queries for XY online.