Truly subquadratic 3SUM and truly subcubic APSP, refuting two central fine-grained complexity hypotheses

A preprint by Josh Alman and Virginia Vassilevska Williams gives deterministic algorithms that solve 3SUM on polynomially bounded integers in time $O(n^{1.9992})$ and all-pairs shortest paths with polynomially bounded integer weights in time $O(n^{2.9995})$, refuting the 3SUM and APSP hypotheses, from an algorithm the paper says an internal Anthropic model found on its own.

What was found

Both hypotheses say the textbook algorithms are essentially optimal: 3SUM, deciding whether three of $n$ integers sum to zero, needs time $n^{2-o(1)}$, and APSP needs $n^{3-o(1)}$. Fine-grained complexity has used them, together with the Exact Triangle hypothesis, as the starting points of many conditional lower bounds, and the abstract describes these as the first polynomial improvements over the textbook algorithms. Everything follows from one new algorithm for thin matrix products: for an $N \times D$ integer matrix $X$ and a $D \times N$ matrix $Y$ with $D \le N^{1/18}$, it computes the entries of $XY$ at any set of at most $N^2/\sqrt{D}$ prescribed positions in $O(N^2/D^{0.063})$ operations, by modifying a variant of Coppersmith's rectangular matrix multiplication algorithm built on a ten-multiplication identity of Schönhage. Read as a graph algorithm, it finds all triangles in sparse lopsided tripartite graphs in truly subquadratic time, and known reductions carry that to Exact Triangle, 3SUM and APSP, and further to the real-valued versions of 3SUM and APSP, the Zero-Weight $k$-Clique hypotheses and three hinted Online Matrix-Vector conjectures. According to the paper's methodology section, an Anthropic employee had an internal research model working on cryptographic constructions based on the average-case hardness of Zero-$k$-Clique; asked to verify and improve them, it instead developed this algorithm, first for the average case and then for the worst case, in one session of 16 million output tokens with no human input. Anthropic shared it with the authors in September 2026, and they simplified, strengthened and extended it and derived the further consequences. After the paper was written, an internal Anthropic model produced a Lean 4 formalization of five headline running-time claims on a word RAM defined in Lean.

Novelty check

Read the abstract, the introduction and the 'Acknowledgments and Methodology' section of arXiv:2610.06783 v1 on 2026-10-16, and the README of the Lean formalization. The abstract presents these as the first polynomial improvements over the textbook algorithms for either problem, and Vassilevska Williams is a co-author of the 2010 work on subcubic equivalences through which the APSP hypothesis is usually stated, so the account of prior work comes from the area's own authorities. The registry had no entry citing this paper and none on either hypothesis. The two Hacker News threads on the preprint raise no technical objection.

The open problem

Also recorded at

Community discussion

Graded author verified for verification and ai-led for autonomy. What these mean.

Cite this entry

whataifound.org. (2026). Truly subquadratic 3SUM and truly subcubic APSP, refuting two central fine-grained complexity hypotheses. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-10-05-3sum-apsp-hypotheses

@misc{whataifound-anthropic-2026-hypotheses,
  title        = {Truly subquadratic 3SUM and truly subcubic APSP, refuting two central fine-grained complexity hypotheses},
  author       = {{whataifound.org}},
  year         = {2026},
  howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
  note         = {Result by Anthropic. Verification: Author verified. Autonomy: AI-led.},
  url          = {https://whataifound.org/finding/2026-10-05-3sum-apsp-hypotheses}
}

Related findings

← All computer science findings in the registry