Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
Josh Alman, Virginia Vassilevska Williams
cs.DS, cs.CC
2026-10-06
First polynomial speedups for 3SUM (O(n^1.9992)) and APSP (O(n^2.9995)) refute two core fine-grained hypotheses; the key algorithm was found by Claude.
3SUM asks whether three of n input integers sum to zero. The textbook algorithm runs in O(n²), and decades of work have added only polylogarithmic factors. APSP (all-pairs shortest paths) is stuck the same way: Floyd–Warshall's O(n³) has only been shaved by a subpolynomial factor. Fine-grained complexity turned this stagnation into two hypotheses, that 3SUM needs n^{2-o(1)} time and APSP needs n^{3-o(1)}. Together with SETH they anchor conditional lower bounds across computational geometry, strings, and dynamic graph problems, and dozens of 'hard' labels trace back to them. This paper gives both problems their first polynomial improvement, and both hypotheses fall.
Every result follows from one algorithm: thin matrix products with sparse output. Given an N×D integer matrix X and a D×N matrix Y with D ≤ N^{1/18}, plus a set W of at most N²/√D output positions, it computes only the entries of XY in W using O(N²/D^{0.063}) operations, polynomially less than the Ω(N²) needed just to write the product down. Spending fewer operations than there are outputs is how the lower bound breaks.
The hard part is counting leaves. Per output entry, each needs 10^m ≈ D^{1.66} leaves, more than the D multiplications of a direct inner product; all savings come from sharing. Each entry has one private leaf, and its other leaves are shared by many entries. Classifying leaves by order, at L = 19m the high-order classes shrink geometrically, so N²/√D wanted entries need only about N²/D^{1/18} leaves in total (the strengthened version reaches O(N²/D^{0.063})).
In graph terms this is Lopsided All-Edges Sparse Triangle: a tripartite graph with two parts of n vertices and a third of n^ε, ε < 0.12, counting triangles through prescribed pairs in O(n^{2-0.063ε}). Known reductions send 3SUM, Exact Triangle, and APSP to this problem, so one algorithm lifts a whole family. A data-structure version preprocesses in O(N²/D^{0.063}) and answers single-entry queries in O(D^{0.437}).
| Problem | Previous best | This paper |
| 3SUM (integers) | O(n²), polylog gains only | O(n^1.9992), deterministic |
| 3SUM (reals) | n² | O(n^1.998), Las Vegas |
| APSP (integer weights) | ≈n³ | O(n^2.9995), deterministic |
| APSP (real weights) | ≈n³ | O(n^2.998), Las Vegas |
| Directed unweighted APSP | O(n^2.5275), Zwick, 20+ years | O(n^{2+µ-ε′′}), first gain not from faster rectangular multiplication |
The Exact Triangle (deterministic O(n^2.9983)), Zero-Weight k-Clique, and (min, +)-convolution hypotheses fall as well, along with the thin-hint regime of the three hinted OMv conjectures. MonoConvolution drops to O(n^1.4999) and 0/1 Knapsack gets its first Õ(n + t^{2-δ}) algorithms. The unaffected list is explicit: SETH, Orthogonal Vectors, OMv without hints, k-SUM and k-XOR for k ≥ 4, and 3SUM-Indexing.
The abstract states that Claude, Anthropic's AI model, discovered the refuting algorithm; the authors, Josh Alman (Columbia) and Virginia Vassilevska Williams (MIT), then understood, simplified, strengthened, and extended it. Claude also verified the main results in Lean 4 with Mathlib.
For theory, this is the biggest shake-up since fine-grained complexity took shape: two of its three pillars are gone, and the reduction web that encoded hardness now distributes the new algorithm across the APSP, 3SUM, and (min, +)-convolution equivalence classes. The paper makes the point itself: reductions were always algorithms, they had just been read as hardness evidence.
For the AI community, the notable part is different: the key construction behind a decades-old barrier came out of an AI model, with machine-checked proofs attached. AI's role in mathematics moved from filling in details to supplying the central idea, and this is among the hardest public data points for that shift. For engineering practice, nothing changes for now. The exponent moves from 2 to 1.9992 and the hidden constants are enormous. The paper answers whether the lower bound holds, not whether software gets faster.
The authors' own list: the constants are enormous and the algorithms are impractical as stated; the exponents likely improve, and variants with slightly better exponents were generated with Claude during the project and deliberately left out; the technique only covers the lopsided regime, it fails once the third part exceeds n^0.12, and the balanced sparse case with its m^{4/3} barrier stands, leaving three-collinear-points in the plane open; k-SUM for k ≥ 4 lacks self-reductions and resists the approach; the main dynamic-matrix-inverse lower bounds from OMv (τ ≈ 0.53) survive, only the fast-query tail falls.
Problems reached only by one-way reductions need a separate look: many dynamic and geometry problems get no new algorithm, they just lose their hardness evidence. Also, the account of how Claude found the algorithm sits in an Acknowledgments and Methodology section outside the extracted text, so the discovery process itself cannot be checked from what was read here. The authors' earlier failed attempts along these lines with the Coppersmith–Winograd identities suggest the construction was not an obvious one.