Can 3SUM and APSP be solved faster than their textbook algorithms?

Two exponents that break long-standing hypotheses

The textbook algorithms for these problems have resisted polynomial improvement for decades: 3SUM, which asks whether three of n given numbers sum to zero, was only sped up by polylogarithmic factors, and APSP, which asks for every pairwise shortest-path distance in an n-vertex graph, was only improved by subpolynomial factors. The paper reports deterministic running times of O(n^1.9992) for 3SUM on n integers of polynomial size and O(n^2.9995) for APSP on directed n-vertex graphs with polynomially bounded integer weights.

Those exponents matter because the 3SUM and APSP hypotheses asserted that no truly subquadratic or truly subcubic algorithm exists — that is, no algorithm with exponent bounded away from 2 or 3. Both hypotheses are now refuted. The savings are small in absolute terms, but they are polynomial, not polylogarithmic, which is the qualitative line the hypotheses drew.

One thin matrix product carries every speedup

All results follow from a single new algorithm for thin matrix products. Take an N×D integer matrix X and a D×N integer matrix Y with D ≤ N^(1/18), and a set W of at most N^2/√D positions in the N×N output. The algorithm computes exactly the entries (XY)[I,J] for (I,J) in W in O(N^2/D^0.063) operations.

The comparison that gives this meaning is against the obvious alternatives: writing down the whole product XY, or computing N^2/√D inner products one at a time, both cost polynomially more. The algorithm is built by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm, itself built from a ten-multiplication identity of Schönhage, so that it performs only the operations needed for the requested entries rather than the full product.

Lopsided triangles connect the product to 3SUM

Read as a graph algorithm, the matrix result solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse lopsided tripartite graphs: two parts have n vertices, but the third has only n^ε vertices for ε < 0.12. The asymmetry is the point — the technique handles instances where one side is far smaller than the others.

Known reductions carry Exact Triangle, and through it 3SUM and APSP, to this lopsided problem, which is how a matrix-product improvement becomes a 3SUM and APSP improvement. The same reductions refute the real-valued versions of the 3SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero-Weight k-Clique hypotheses, and three rectangular hinted Online Matrix–Vector conjectures of van den Brand, Nanongkai, and Saranurak, and yield polynomial speedups for a variety of other problems.

Preprocessing trades against query time and sparsity

The paper also gives a data structure version that answers queries for single entries of XY that are not known in advance. For every ε below ε* = ln4/(5 ln10) ≈ 0.1204 and every q > 0, matrices with 2 ≤ D ≤ N^ε can be preprocessed deterministically in O(N^2 log^2 D / D^γ) time and space, after which any single entry can be computed deterministically in O(D^q log D) time.

The explicit parameter table makes the trade-off concrete. A larger ratio c = L/m yields a larger saving exponent γ but a smaller ε, meaning the product must be thinner; a slower query or a sparser set W also allows a larger γ. The setting used for the headline results is c = 21 with switching order t = m/9, giving preprocessing in O(N^2/D^0.063) and single-entry queries in O(D^0.437), so that any W with |W| ≤ N^2/√D is handled within O(N^2/D^0.063).

The technique stops at D beyond N^0.1204

The constant ε* ≈ 0.1204 is the upper limit on how unbalanced the product can be for this construction. The paper states that pushing c down toward 10 gives this limit, so the lopsided triangle result covers only ε < 0.12, and the refutation of the hinted Online Matrix–Vector conjectures applies only in the regime τ1 < 0.1204 τ2.

That boundary has consequences the authors spell out. The balanced case of All-Edges Sparse Triangle, with m edges, is not sped up, and it remains the target of several lower-bound reductions from 3SUM and Exact Triangle. The dynamic-algorithm trade-offs derived from the refuted conjectures remain supported by their unrefuted forms at parameters such as τ ≈ 0.53, where the products are far from thin enough for this construction; only the small-τ end, where queries are fastest, loses its conditional optimality.

Reductions that once proved hardness now lose exponent

Each algorithm composes known reductions with the matrix theorem, and the authors note that many reductions lose a constant fraction of the saving. The reduction from Exact Triangle to Lopsided All-Edges Sparse Triangle keeps only half of the saving in the exponent, while the reductions from 3SUM and APSP to Exact Triangle keep a half and a third respectively.

These reductions were designed to prove hardness, where only some polynomial saving mattered; used as algorithms, how much they keep becomes the deciding factor. The authors also note that the exponents presented can already be improved slightly without much work — for APSP, by not going through the decision version of Exact Triangle, and for 3SUM, via a direct randomized reduction to offline Set Disjointness — but they prioritized a simpler presentation over further small gains.

Which hypotheses should replace 3SUM and APSP

The paper's own priority is not the specific exponents but the question of what comes next. It suggests restricting the hypotheses to combinatorial algorithms, or adopting the hypothesis that the balanced case of All-Edges Sparse Triangle with m edges needs m^(4/3−o(1)) time, since that balanced case is untouched here and still supports many hardness reductions.

Problems that are only known to be 3SUM-hard or APSP-hard, rather than equivalent to 3SUM or APSP, get no faster algorithms, because the reductions run the other way; the authors cite deciding whether n planar points contain three on a line, whose fastest known time remains O(n^2), as an example. The same holds for k-SUM with k ≥ 4, 3SUM-Indexing, Online Matrix–Vector without hints, and Orthogonal Vectors. The most decision-relevant split is therefore between the lopsided instances this technique reaches and the balanced instances it does not.

An AI model produced the core algorithm

The methods section records an unusual provenance. An Anthropic employee used an internal research model to investigate open problems in the theory of cryptography, including constructions based on the average-case hardness of Zero-k-Clique; the model was tasked with verifying and improving those constructions but instead developed this algorithm, first for the average case and then the worst case, in a session using 16M output tokens with no human input.

Anthropic shared the algorithm with the authors in September 2026 under a confidentiality agreement. After the paper was written, an internal research model certified the main results in the Lean 4 proof assistant with Mathlib, covering Exact Triangle in O(n^2.9983) time, 3SUM in O(n^1.9992) time with the (min,+) product and APSP in O(n^2.99942) time, and the Zero-Weight case of the k-Clique corollary. The authors state they used Claude for writing, figures, and checking mathematical details, and take full responsibility for the contents.

Watch the lopsided threshold, not the headline exponent

For readers deciding how much weight to give this result, the informative quantity is not the fourth decimal of n^1.9992 but the threshold D ≤ N^0.1204. Everything the paper claims about 3SUM, APSP, and the refuted conjectures flows through thin products inside that regime, and the authors explicitly flag that a different technique would be needed to reach a middle part larger than n^0.12, such as the n^1/2 that arises in an approach to girth approximation.

The paper's own framing points the same way: any improvement to the matrix theorem carries over to all the other speedups, and the authors do not know the true complexity of computing a set W of entries of a thin product as a function of D and |W|. The practical reading is that the balanced All-Edges Sparse Triangle case and the problems only 3SUM-hard or APSP-hard remain the places where the old hypotheses still do work.

Sources used in this answer