Researchers Break 3SUM and APSP Hypotheses With New Algorithms
Deterministic algorithms achieve subquadratic time for 3SUM and subcubic time for APSP, backed by a Lean 4 proof verification repository.
Key takeaways
- Researchers Josh Alman and Virginia Vassilevska Williams published deterministic algorithms running in O(n^1.9992) for 3SUM and O(n^2.9995) for APSP.
- The findings refute the standard 3SUM and APSP hypotheses, as well as the Exact Triangle and Zero-Weight k-Clique hypotheses.
- The speedups stem from a new thin matrix product algorithm based on Schönhage's ten-multiplication identity and Coppersmith's techniques.
- The core claims have been formalized and verified in Lean 4 on a word RAM model in an Anthropic-hosted GitHub repository.
In a 76-page research paper submitted on October 5, 2026, researchers Josh Alman and Virginia Vassilevska Williams presented the first polynomial improvements over long-standing textbook algorithms for the 3SUM and All-Pairs Shortest Paths (APSP) problems. Published on arXiv.org, the work demonstrates deterministic algorithms solving 3SUM in $O(n^{1.9992})$ time and APSP in $O(n^{2.9995})$ time on directed graphs with polynomially bounded integer weights, formally refuting the 3SUM and APSP hypotheses.
Alongside the theoretical paper, an accompanying Lean 4 formalization was released on GitHub by Anthropic, establishing machine-checked verification for the headline results on a word RAM model.
Refuting Foundational Complexity Hypotheses
The new results systematically refute the 3SUM hypothesis, the APSP hypothesis, the Exact Triangle hypothesis, and the Zero-Weight $k$-Clique hypotheses.
According to the arXiv preprint, the reductions also refute the real-valued versions of the 3SUM and APSP hypotheses, alongside three rectangular hinted Online Matrix-Vector conjectures originally posed by van den Brand, Nanongkai, and Saranurak. The framework additionally delivers polynomial speedups for multiple related computational problems.
Thin Matrix Products and Sparse Lopsided Graphs
The breakthroughs trace back to a unified algorithmic technique for thin matrix multiplication. The authors consider an integer matrix $X$ of size $N imes D$ and an integer matrix $Y$ of size $D imes N$ where $D \le N^{1/18}$. For any designated subset $W$ containing at most $N^2/\sqrt{D}$ positions, the algorithm computes all entries $(XY)[I,J]$ for $(I,J) \in W$ in $O(N^2/D^{0.063})$ operations.
This runtime is strictly less than the operations needed to compute the entire matrix product $XY$ or evaluate $N^2/\sqrt{D}$ inner products individually. The researchers designed this method by adapting Coppersmith's rectangular matrix multiplication algorithm, utilizing an underlying ten-multiplication identity discovered by Schönhage to execute only the necessary operations for target positions in $W$.
When translated to graph theory, this technique solves the All-Edges Sparse Triangle problem in truly subquadratic time on sparse tripartite graphs where two vertex sets contain $n$ elements while the third contains $n^\varepsilon$ vertices for $\varepsilon < 0.12$. By applying known reductions, Exact Triangle, and hence 3SUM and APSP, reduce to this problem.
Machine-Checked Formalization in Lean 4
To ensure the correctness of the theoretical bounds, key components of the paper were formalized in the Lean 4 proof assistant. The formalization, structured under Anthropic's formal-math repository, compiles against Lean v4.33.1 and Mathlib v4.33.1.
The repository's primary entry file, EndStatement.lean, contains 139 lines that depend solely on Lean's core library without importing Mathlib. It states five headline claims on a word RAM model with $O(\log n)$-bit words and contains no proof, while the accompanying library proves them:
- Exact Triangle: Solved in $O(n^{3-0.0017})$ time.
- 3SUM: Solved in $O(n^{1.9992})$ time.
- (min,+)-product: Solved in $O(n^{2.99942})$ time.
- APSP: Solved in $O(n^{2.99942})$ time.
- Zero-Weight $k$-Clique: Solved in $O(n^{k-0.0017\lfloor k/3 floor})$ time for every $k \ge 3$.
Implementation Scope and Verified Claims
The formal proof library models a word RAM machine with nine fundamental instructions operating on integer-addressed memory cells holding $W$-bit words. The machine supports basic addition, subtraction, modular multiplication, conditional jumps on negative values, and indexed memory loads and stores, without relying on bitwise shifts or division.
The repository documentation notes that while the deterministic integer-input algorithms and structural reductions are fully verified in Lean, the running times for Las Vegas algorithms on real RAM inputs and certain rectangular matrix multiplication exponent bounds were left as explicit hypotheses rather than proved end-to-end within the machine model.
Frequently asked questions
What are the new running times achieved for 3SUM and APSP?
The deterministic algorithms achieve a runtime of O(n^1.9992) for 3SUM on n integers of polynomial size, and O(n^2.9995) (with an alternate bound of O(n^2.99942) in the formalization) for All-Pairs Shortest Paths on directed graphs with polynomially bounded integer weights.
What foundational hypotheses are refuted by this work?
The paper refutes the 3SUM hypothesis, the APSP hypothesis, the Exact Triangle hypothesis, the Zero-Weight k-Clique hypotheses, and three rectangular hinted Online Matrix-Vector conjectures.
What role does Lean 4 play in this research?
Lean 4 was used to create a machine-checked formalization of the paper's core theorems on a word RAM model, verified using Lean v4.33.1 and hosted in Anthropic's formal-math repository.
Sources
- Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided GraphsarXiv.org · Official
- formal-math/3sum-apsp at main · anthropics/formal-mathGitHub · Official
How this story was made: the newsroom picked it up from Reddit, gathered the full text of the sources above, and drafted it with AI assistance. Every factual claim was then checked against those sources before publishing (38 claims checked). Illustrations marked as AI-generated are not photographs. Spotted an error? Tell us.
Published October 7, 2026 at 01:09 UTC
