An Anthropic model found the first algorithms that beat the textbook running times for two of computer science’s most studied problems, 3SUM and all-pairs shortest paths (APSP), by a polynomial factor. The proof is a paper Josh Alman (Columbia) and Virginia Vassilevska Williams (MIT) posted to arXiv on October 5, 2026: 3SUM in O(n^1.9992) time and APSP in O(n^2.9995), both deterministic, which refutes the 3SUM and APSP hypotheses that a large part of fine-grained complexity theory rests on. The paper credits the core algorithm to Claude in plain words: “Claude, an AI model developed by Anthropic, discovered the algorithm that refutes the 3SUM, APSP, and Exact Triangle hypotheses.” This page reads the arXiv paper (v1, 17:44 UTC on October 5), its full text and Anthropic’s Lean formalization, as of October 6, 2026. Anthropic had not published its own post about the result when we checked its site at 14:20 UTC.
On this page · 7 sectionsOpen
A paper posted to arXiv on October 5, 2026 gives the first polynomial speedups for 3SUM and APSP: O(n^1.9992) and O(n^2.9995), both deterministic.
The authors, Josh Alman of Columbia and Virginia Vassilevska Williams of MIT, credit the core algorithm to Claude, an AI model developed by Anthropic.
The result refutes the 3SUM and APSP hypotheses of fine-grained complexity, plus the Exact Triangle and Zero-Weight k-Clique hypotheses.
An internal Anthropic research model found it while checking cryptographic constructions, in a 16 million output token session with no human input.
Anthropic certified the main deterministic results in Lean 4 with Mathlib and published the formalization on GitHub.
It is a preprint: outside experts have only begun reviewing it, and Anthropic had not published its own write-up on October 6.
§ 01What the paper proves
3SUM asks whether any three of n numbers add up to zero. APSP asks for the shortest path between every pair of vertices in a weighted graph. Both have simple textbook algorithms, quadratic for 3SUM and cubic for APSP, and decades of work had only shaved small, slower-than-polynomial factors off them. Fine-grained complexity turned that stubbornness into hypotheses: assume 3SUM needs n^2 time and APSP needs n^3, and many other problems are provably no easier. The paper’s abstract: “This refutes the 3SUM and APSP hypotheses of fine-grained complexity theory.”
| Problem | Textbook bound | New bound | Kind |
|---|---|---|---|
| 3SUM, integers of polynomial size | n^2 | O(n^1.9992) | Deterministic |
| APSP, directed, polynomially bounded integer weights | n^3 | O(n^2.9995) | Deterministic |
| Exact Triangle (Theorem 19) | n^3 | O(n^2.9983) | Deterministic |
| 3SUM on real numbers | n^2 | O(n^1.998) expected | Las Vegas, randomized |
| Zero-Weight k-Clique (Corollary 39) | n^k | O(n^(k-0.0017⌊k/3⌋)) | For every k of 3 or more |
Everything follows from one new algorithm for a narrow kind of matrix product. Multiply a tall, thin integer matrix by a short, wide one, but only want a sparse set of the output’s entries: the paper computes those entries faster than it would take to write the full product down. In graph terms it finds triangles quickly in sparse lopsided graphs where one of the three vertex groups is tiny, and known reductions carry that speedup to Exact Triangle, then to 3SUM and APSP. The construction modifies a variant of Don Coppersmith’s 1982 rectangular matrix multiplication algorithm, built on a ten-multiplication identity of Arnold Schönhage, to skip the work that only feeds unwanted entries.
The improvements are small in absolute terms and large in what they break. At a billion inputs, n^2 divided by n^1.9992 is about 1.017, under a 2% difference before constant factors, which the paper does not claim are small. The point is that the exponent moved at all, after decades in which it did not.
§ 02How Claude found it
The paper’s “Acknowledgments and Methodology” section tells the story, and the account below follows it line by line.
| Step | What the paper says |
|---|---|
| The task | An Anthropic employee used an internal research model on open problems in cryptography, including constructions based on the average-case hardness of Zero-k-Clique |
| The turn | Claude was asked to verify and improve those constructions and instead developed this algorithm, first for the average case, then the worst case |
| The run | 16M output tokens, with no human input |
| The handoff | Anthropic shared the algorithm with the authors in September 2026 under a confidentiality agreement, offered compensation, and gave access to the public version of Claude |
| What the authors added | Understood, simplified, strengthened and extended it; the data structure version (Section 4) and its link to Hinted OMv are theirs |
| What was left out | A different reduction Claude shared was not used; the authors relied on known reductions instead |
| The proof check | After the paper was written, Anthropic used an internal research model to certify the main results in Lean 4 with Mathlib |
| Writing help | The authors used Claude for writing, figures and checking mathematical details |
Two details are worth reading twice. The model was not asked to attack 3SUM. It was checking cryptographic constructions that assume a related problem is hard, and it found an algorithm that showed the assumption was weaker than believed. And the run had no human in it: “The session used 16M output tokens with no human input.” The authors are explicit about ownership of the paper itself: “The authors take full responsibility for this paper.” They also note the work was done in their individual capacities, not for Columbia or MIT.
§ 03The Lean proof, and what it does not cover
Anthropic published the formalization on GitHub, in a commit dated 04:00 UTC on October 6. Its README says the five headline claims sit in one file, EndStatement.lean, which has 139 lines, imports nothing and contains no proof, so a reader who wants to trust the claims only has to read that file and check that the rest of the library builds.
| Item | Status in Lean |
|---|---|
| Exact Triangle in O(n^2.9983) (Theorem 19) | Proved about programs of a word RAM |
| 3SUM in O(n^1.9992) (Theorem 22) | Proved about programs of a word RAM |
| (min,+)-product and APSP in O(n^2.99942) (Theorem 22) | Proved about programs of a word RAM |
| Zero-Weight k-Clique (Corollary 39, weight-zero case) | Proved about programs of a word RAM |
| Running times for real-number inputs (including the O(n^1.998) 3SUM bound) | Not proved for any machine |
| Numbered lemmas of Sections 2 to 5 | Proved as mathematics, without running times |
The APSP exponent in Lean, 2.99942, is the precise form of the 2.9995 in the abstract. The randomized real-number results are the part a reader still has to take from the paper.
§ 04What it does and does not change
The paper lists what falls with 3SUM and APSP: the real-valued versions of both hypotheses, the Exact Triangle hypothesis, the Zero-Weight k-Clique hypotheses, and three rectangular hinted Online Matrix-Vector conjectures. Results that were proved conditional on those hypotheses lose that footing.
The paper does not claim to refute the Strong Exponential Time Hypothesis (SETH): its own list of problems that get faster algorithms leaves out CNF-SAT and Orthogonal Vectors, the problems at the base of SETH-based hardness.
It is also a preprint. Version 1 went up on October 5, and the Lean check covers the main deterministic results, but outside experts have only begun reading it. Mahdi Ch. (@mahdi_tcs_) reacted on X about nine hours after the listing, and the post passed 430,000 views by midday on October 6.
§ 05What this means if you run agents
The useful lesson is about the run, not the theorem. A model left alone on a well-posed research task, with 16 million output tokens and no one steering, came back with something the field had not found, and the claim arrived with a machine-checkable proof. That is the shape of long, unattended agent work everywhere: a clear task, a long budget, and a check you can trust at the end.
Two cautions keep it honest. The model that did this was an internal Anthropic research model, not the public Claude; the authors got access to the public version. And CellCog’s AI employees, which run on Claude Opus 5.5 at every tier, do business work, research, writing and code, not unreviewed mathematics. What carries over is the pattern: give an agent a real task and room to work, and build the check into the job.
§ 06What we are watching
- An Anthropic write-up of how the internal model found the algorithm.
- Expert verification and peer review of the paper beyond the Lean check.
- Follow-up exponents: whether others push 1.9992 and 2.9995 lower now that the barrier is broken.
- The model itself: whether the internal research model behind this, or its capabilities, reaches the public Claude.
§ 07Sources
- Josh Alman and Virginia Vassilevska Williams, “Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs”, arXiv 2610.06783 v1, October 5, 2026, and full text (PDF)
- Anthropic, 3sum-apsp Lean 4 formalization, read October 6, 2026
- Mahdi Ch. on X, reaction post, October 6, 2026
Q1Did Claude really solve 3SUM?
Claude found an algorithm that beats the textbook quadratic time for 3SUM by a polynomial factor, O(n^1.9992) for integers of polynomial size. It did not find a linear-time algorithm. The paper by Josh Alman and Virginia Vassilevska Williams credits the core algorithm to an internal Anthropic research model.
Q2What is the 3SUM hypothesis?
It is the assumption that deciding whether three of n numbers sum to zero needs roughly n^2 time. Many lower bounds in fine-grained complexity were proved conditional on it. The new paper refutes it, along with the APSP hypothesis that all-pairs shortest paths needs roughly n^3 time.
Q3Was the proof checked?
Yes, in part. After the paper was written, Anthropic used an internal model to certify the main deterministic results in Lean 4 with Mathlib, and published the formalization on GitHub. The running times for real-number inputs are not formalized.
Q4Does this refute SETH?
No. The paper does not claim to, and its list of problems that get faster algorithms leaves out CNF-SAT and Orthogonal Vectors, the problems at the base of SETH-based hardness.
Q5Which Claude found it?
An internal Anthropic research model, not the public Claude. The paper says Anthropic shared the algorithm with the authors in September 2026 under a confidentiality agreement and gave them access to the public version of Claude.