Alman and Williams crack textbook 3SUM and APSP bounds

Josh Alman and Virginia Vassilevska Williams say they have the first polynomial improvement over the textbook algorithms for two of the oldest barriers in fine-grained complexity. Their 76-page preprint, posted to arXiv on October 5, 2026, gives deterministic algorithms running in O(n^1.9992) time for 3SUM on n integers and O(n^2.9995) time for All-Pairs Shortest Paths on n-vertex directed graphs with polynomially-bounded integer weights.

The paper's own words: "the first polynomial improvements over the textbook algorithms for 3SUM and All-Pairs Shortest Paths (APSP)."

The savings in the exponent are tiny. The downstream consequences are not. The authors say the result refutes four load-bearing conjectures of the area: the 3SUM hypothesis, the APSP hypothesis, the Exact Triangle hypothesis, and the Zero-Weight k-Clique hypothesis. These are the assumptions a decade of conditional lower bounds has been built on top of.

The engine is a thin matrix multiplication subroutine. Given an N by D matrix X and a D by N matrix Y where D is at most N^(1/18), the algorithm computes a specified sparse subset of up to N^2/sqrt(D) entries of XY in O(N^2/D^0.063) operations, polynomially faster than the obvious approach. The gain cascades to triangle-finding in sparse lopsided graphs, and from there to 3SUM and APSP.

Two of the researchers we follow had already shared the link within hours.