We give the first polynomial improvements over the textbook algorithms for 3SUM and All-Pairs Shortest Paths (APSP): we show how to deterministically solve 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. This refutes the 3SUM and APSP hypotheses. Using known reductions, we also refute 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, 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×D integer matrix and Y a D×N integer matrix with D ≤ N^{1/18}, and let W be any set of at most N^2/√D positions. We compute the entries (XY)[I, J], (I, J)∈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/√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^{ε} vertices for ε<0.12. By known reductions, Exact Triangle, and hence 3SUM 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. Submission history From: Josh Alman [view email] [v1]Mon, 5 Oct 2026 17:44:29 UTC (93 KB).
Source: Hacker News · Summarized by HeadlinesBriefing