Claude discovers an algorithm that refutes the 3SUM and APSP hypotheses
Truly subquadratic 3SUM and truly subcubic APSP (Alman & Vassilevska Williams, Lean-verified)
Event confirmedAwaiting review
Importance: historic (5 of 5)Status
- Claim
Event confirmedAwaiting review
- Our reporting
- High confidence
- Verification
- Lean-verified
- Importance
- Historic (5 of 5)
- Last verified
- 13 October 2026
Your AI and this story
- GPT-6.2 Astra127 days after its cutoff
- Claude Opus 5.597 days after its cutoff
- Gemini 4 Hydrogen188 days after its cutoff
- Grok 4.7127 days after its cutoff
None of these four assistants can know about it. The closest, Claude Opus 5.5, stops 97 days before it.
Key facts
- Paper: ‘Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs’, Josh Alman (Columbia) and Virginia Vassilevska Williams (MIT), arXiv 2610.06783, cs.DS, Oct 5, 2026
- Results: deterministic 3SUM on n polynomial-size integers in O(n^1.9992); APSP on directed graphs with polynomially bounded integer weights in O(n^2.9995); Exact Triangle in O(n^2.9983); Zero-Weight k-Clique in O(n^(k−0.0017⌊k/3⌋))
- Refuted (with known reductions): the 3SUM and APSP hypotheses, their real-valued versions, 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
- Core idea: an algorithm for thin matrix products that computes a sparse set of entries of XY polynomially faster than writing XY down, by modifying a variant of Coppersmith’s rectangular matrix multiplication built from a ten-multiplication identity of Schönhage; as a graph algorithm it solves All-Edges Sparse Triangle on sparse lopsided tripartite graphs in truly subquadratic time
- How it was found (paper): ‘An Anthropic employee used an internal research model to investigate open problems in the theory of cryptography’ (constructions based on average-case hardness of Zero-k-Clique). ‘Claude was tasked with verifying and improving the constructions, but instead developed this algorithm, first for the average case, then for the worst case. The session used 16M output tokens with no human input.’
- Anthropic shared the algorithm with the authors in September 2026 under a confidentiality agreement and offered compensation; the authors simplified, strengthened and extended it (the data-structure version and the Hinted OMv connection are theirs)
- Lean: after the paper was written, Anthropic used an internal model to certify Theorems 19 and 22 and the Zero-Weight case of Corollary 39 in Lean 4 + Mathlib, with all lemmas they rely on; repo anthropics/formal-math (3sum-apsp), checked with the Comparator tool, standard axioms only. Not formalized: real-input Las Vegas algorithms, Theorem 33, matrix-multiplication exponent values and the Section 5.1 running times
- Context: the O(n^2) 3SUM algorithm had only been improved by polylog factors (Grønlund–Pettie 2014 and later), and APSP by subpolynomial factors (Williams 2018); these hypotheses underpin many conditional lower bounds
Show 2 more
- Verification status: preprint plus machine-checked Lean certificate of the main theorems; no peer review yet; reactions not yet found at 07:30 CEST Oct 6; by Oct 9 the Hacker News thread had 109 points and 49 comments, mostly summarising Claude’s role, with one technical question on whether the sparse lopsided graph structure carries the subquadratic gain; no public expert assessment found
- Related independent work (Oct 7): Fischer (MPI-INF), Polak and Schmidt (Bocconi), ‘3SUM Is Really Hard: A Real-to-Integer Reduction’ (arXiv 2610.10153), prove that a truly subquadratic Integer 3SUM algorithm yields a truly subquadratic Real 3SUM algorithm (comparison-addition model), answering an open question of Chan, Vassilevska Williams and Xu (STOC 2022). The paper does not cite 2610.06783 and has no AI disclosure; it was written under the assumption that 3SUM is hard
What happened
Fine-grained complexity rests on a few hypotheses: that 3SUM needs about n² time, APSP about n³ time, and so on. Many “conditional lower bounds” assume them. Alman and Vassilevska Williams, both leading researchers in the area, now show polynomial speedups for both, so all those bounds lose their basis. The improvement in the exponent is tiny (0.0008 for 3SUM), but any polynomial improvement refutes the hypotheses.
Per the paper’s “Acknowledgments and Methodology”, the algorithm came from Claude: an Anthropic employee was using an internal research model on cryptographic constructions built on the average-case hardness of Zero-k-Clique. Instead of verifying them, the model broke the assumption, first on average and then in the worst case, in one session of 16M output tokens. Anthropic passed the algorithm to the two authors in September, and certified the final paper’s main theorems in Lean.
Why it matters
This is the most significant theoretical-computer-science result credited to an AI so far, and the first where a frontier model, unprompted, overturned a widely believed conjecture rather than proving one that experts expected to be true. The Lean certificate addresses correctness; whether the method generalises (e.g. to SETH or Orthogonal Vectors) is open. The paper was found on Oct 6 by a manual arXiv scan; Anthropic had not yet announced it on its own channels at that time.
What is disputed or not yet verified
| Verification | Preprint; main theorems formally verified in Lean 4/Mathlib by an Anthropic internal model |
|---|
Sources
4 sources from 3 sites. Numbers match the chips in the text.
4 sources: 3 primary, 1 reaction
Primary
- arXiv 2610.10153: 3SUM Is Really Hard: A Real-to-Integer Reduction (Fischer, Polak, Schmidt)arxiv.org, paper
- arXiv 2610.06783: Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphsarxiv.org, paper
- GitHub: anthropics/formal-math, 3sum-apsp Lean formalizationgithub.com, code
Reactions
- Hacker News discussion (109 points, Oct 6)news.ycombinator.com, discussion
Changes
- Related: the catalogue that lists this result is now October 2026: the arXiv stream of conjectures settled with disclosed AI help continues (the October blocks were split out of the summer catalogue)
- Added the independent real-to-integer 3SUM reduction (arXiv 2610.10153)
- Rechecked reactions (HN 109 points; no expert assessment found)
- Summary states that the Lean certificate covers the main theorems only (a model reading /science/ generalised it to the whole proof)
- Filed (arXiv scan of the Oct 5 listing; PDF read with pdftotext)