New algorithms beat classic limits on two core computing problems
A preprint proves faster deterministic methods for 3SUM on integers and All-Pairs Shortest Paths on directed graphs, refuting both longstanding computational hypotheses.
Edited by Boris Djordjevic · Paperfoot
A preprint proves the first polynomial improvements over textbook algorithms for 3SUM on n integers of polynomial size and All-Pairs Shortest Paths on directed n-vertex graphs with polynomially bounded integer weights. The proof establishes deterministic algorithms that solve 3SUM in O(n^(1.9992)) time and All-Pairs Shortest Paths in O(n^(2.9995)) time. This refutes the 3SUM and All-Pairs Shortest Paths hypotheses. Using known reductions—mathematical transformations between problems—the work also refutes their real-valued versions, the Exact Triangle hypothesis, the Zero-Weight k-Clique hypotheses, and three related matrix conjectures.
All results follow from a single new algorithm for multiplying thin integer matrices. The method calculates target matrix entries in polynomially fewer operations than computing them individually. Interpreted as a graph algorithm, it solves the All-Edges Sparse Triangle problem on sparse three-part graphs, to which 3SUM and shortest paths reduce.
Why it matters
The mathematical proof settles decades-old open questions by demonstrating that standard textbook runtimes for these foundational problems are not fundamental barriers. This disproves key complexity hypotheses that researchers have used to conjecture the difficulty of many other algorithmic tasks.
Caveats
The theoretical bounds require polynomial bounds on integer weights, and the abstract does not report practical implementations or empirical runtimes. Additionally, the work is a preprint that has not yet undergone peer review.
In this paper
thin matrix products
- Methods
- Full (this paper)Mult (this paper)Strassen's algorithm (baseline)Coppersmith's rectangular matrix multiplication algorithm
Results
- Full, time, n integers of polynomial size: O(n^(1.9992)); Full, time, directed n-vertex graphs with polynomially bounded integer weights: O(n^(2.9995))
… 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 …
Abstract
- Full, operations, D≤ N^(1/18), and let W be any set of at most N2/√ D positions: O(N2/D^(0.063))
We compute the entries (XY)[I,J], (I,J)∈ W, in O(N2/D^(0.063)) operations, which is polynomially less than the time needed to write down XY or to compute N2/√ D inner products one by one.
Abstract
- Full, time, D≥ 4 be a power of four and N≥ D^{18}: O(N^{2}\log^{2} D/D^{1/18})
Given as input matrices X\in\mathbb{Z}^{N× D} and Y\in\mathbb{Z}^{D× N}, whose entries are integers of absolute value at most N^{O(1)}, as well as a set W of at most N^{2}/\sqrt{D} positions of an N× N matrix, the entries (XY)[I,J], (I,J)\in W, can be computed deterministically in time O(N^{2}\log^{2} D/D^{1/18 …
Theorem 5.
- Full, operations: O(L\cdot 10^{L})
Hence, Full uses \sum_{k=0}^{L}10^{k}\cdot O(7^{L-k}+10^{L-k})=O(L\cdot 10^{L}) operations in total, which is not much more than the 10^{L} multiplications.
2.3.1 The recursion
What it shows
- Entries of a thin matrix product at a sparse set of positions can be computed deterministically in O(N^2 log^2 D / D^(1/18)) time.
Given as input matrices X\in\mathbb{Z}^{N× D} and Y\in\mathbb{Z}^{D× N}, whose entries are integers of absolute value at most N^{O(1)}, as well as a set W of at most N^{2}/\sqrt{D} positions of an N× N matrix, the entries (XY)[I,J], (I,J)\in W, can be computed deterministically in time O(N^{2}\log^{2} D/D^{1/18 …
Theorem 5.
Quoted word for word from the full text on arXiv.
The paper
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
arXiv, Oct 5, 2026, Open access, CC BY, Preprint, not peer-reviewed
doi.org/10.48550/arxiv.2610.06783
arXiv:2610.06783v1 in cs.DS, also cs.CC
Comments: 76 pages
Cite as BibTeX
@misc{alman2026truly,
title = {Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs},
author = {Alman, Josh and Williams, Virginia Vassilevska},
year = {2026},
eprint = {2610.06783},
archivePrefix = {arXiv},
primaryClass = {cs.DS},
doi = {10.48550/arxiv.2610.06783},
url = {https://arxiv.org/abs/2610.06783}
}
