← All papers
First page of Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Josh Alman, Virginia Vassilevska Williams

cs.DS Oct 5, 2026 · v1 cs.CC
The paper's main results were certified by an Anthropic research model (Claude) in Lean 4 with Mathlib after the paper was written.
We give the first polynomial improvements over the textbook algorithms for $3$SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve $3$SUM 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. This refutes the $3$SUM and APSP hypotheses. Using known reductions, we also refute the real-valued versions of the $3$SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight $k$-Clique hypotheses, and the three rectangular hinted Online Matrix–Vector conjectures of van den Brand, Nanongkai, and Saranurak, and we give polynomial speedups for a variety of other problems. All of these results follow from a single new algorithm for thin matrix products. Let $X$ be an $N\times D$ integer matrix and $Y$ a $D\times N$ integer matrix with $D\le N^{1/18}$, and let $W$ be any set of at most $N^2/\sqrt D$ positions. We compute the entries $(XY)[I,J]$, $(I,J)\in W$, in $O(N^2/D^{0.063})$ operations, which is polynomially less than the time needed to write down $XY$ or to compute $N^2/\sqrt D$ inner products one by one. We design this algorithm by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, built from a ten-multiplication identity of Schönhage, to perform only the operations needed for the entries in $W$, and show that few operations are needed. Interpreted as a graph algorithm, this solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs where two parts have $n$ vertices but one part has $n^{\varepsilon}$ vertices for $\varepsilon<0.12$. By known reductions, Exact Triangle, and hence $3$SUM and APSP, reduce to this problem. We also give a data structure version that answers queries for single entries of $XY$, not known in advance.

3SUM and All-Pairs Shortest Paths (APSP) had no known polynomial improvements over the textbook O(n^2) and O(n^3) algorithms. Fine-grained complexity hypotheses assumed none were possible.

The core is a new algorithm that computes a chosen set W of entries of a thin product XY, where X is N×D, Y is D×N, and D ≤ N^{1/18}. It modifies a variant of Coppersmith's rectangular matrix multiplication algorithm, built from Schönhage's ten-multiplication identity, so that only operations needed for the wanted entries are performed. As a graph algorithm, this solves All-Edges Sparse Triangle on lopsided tripartite graphs, and known reductions (made deterministic here) carry the result to Exact Triangle, 3SUM and APSP. The algorithm was originally found by Claude, and the main results were later certified in Lean 4 with Mathlib.

The paper gives deterministic algorithms for 3SUM in O(n^{1.9992}) time and for APSP with polynomially bounded integer weights in O(n^{2.9995}) time, refuting both hypotheses. It also refutes the real-valued 3SUM/APSP hypotheses, the Exact Triangle and Zero-Weight k-Clique hypotheses, and the rectangular hinted OMv conjectures, and provides a data-structure version for single-entry queries of XY.