First polynomial speedups for 3SUM and APSP overturn long-standing complexity conjectures

Two textbook barriers fall

A new arXiv preprint claims the first polynomial improvements over the textbook algorithms for 3SUM and All-Pairs Shortest Paths (APSP), two of the most intensively studied problems in theoretical computer science. The paper, submitted by Josh Alman on 5 October 2026 and surfaced on the Hacker News front page, reports a deterministic algorithm for 3SUM on n integers of polynomial size running in O(n^1.9992) time, and an algorithm for APSP on directed n-vertex graphs with polynomially bounded integer weights running in O(n^2.9995) time.

For context: the standard 3SUM approach — sort the input, then sweep with two pointers — takes quadratic time, and the classical Floyd–Warshall algorithm for APSP takes cubic time. Both exponents have resisted constant improvement for decades, to the point that fine-grained complexity theory enshrined that resistance as the 3SUM hypothesis and the APSP hypothesis: the assumptions that no algorithm can shave a fixed constant off those exponents. According to the abstract, the new results refute both.

One algorithm behind everything

Rather than attacking each problem separately, the paper derives everything from a single new routine for thin matrix products. Let X be an N×D integer matrix and Y a D×N integer matrix, where D is at most N^(1/18). Given any set W of at most N^2/√D positions, the routine computes the entries of the product XY at those positions in O(N^2/D^0.063) operations — which, as the abstract notes, is polynomially less than either writing down the full product or computing the required inner products one at a time.

The construction modifies a variant of Coppersmith's rectangular matrix multiplication algorithm, itself built from a ten-multiplication identity due to Schönhage, so that it performs only the operations needed for the entries in W, and proves that few operations suffice.

Read as a graph algorithm, the routine solves the All-Edges Sparse Triangle problem — deciding, for every edge, whether it lies in a triangle — in truly subquadratic time on sparse lopsided tripartite graphs, meaning graphs where two sides have n vertices but the third has only n^ε vertices for ε below 0.12. Known reductions take Exact Triangle, and through it 3SUM and APSP, down to this problem. The paper also describes a data-structure version that answers queries for individual entries of XY that are not known in advance.

A cascade of refuted conjectures

The 3SUM and APSP hypotheses are not isolated conjectures; they anchor conditional lower bounds throughout fine-grained complexity. Using known reductions, the paper also refutes the real-valued versions of the 3SUM 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. It further reports polynomial speedups for a variety of other problems.

Why it matters

The immediate practical payoff is likely limited: an exponent of 1.9992 versus 2 only becomes meaningful at enormous input sizes, and this is an unrefereed preprint whose proofs will need close scrutiny before the claims are settled. Theoretically, however, the result is a landmark. It resolves two of the field's oldest and most consequential conjectures in the negative, and it demonstrates that the existing machinery of rectangular matrix multiplication — rather than some fundamentally new technique — was enough to break them. Because a significant body of conditional hardness results rested on the now-refuted hypotheses, parts of the fine-grained complexity landscape will have to be redrawn.