# Claude's 3SUM and APSP Algorithm: What the Paper Proves

> An Anthropic model found the first polynomial speedups for 3SUM and APSP. The Alman and Vassilevska Williams paper, the Lean proof, and what it changes.

- Author: Nitish Garg, Founder & CEO, CellCog
- Published: 2026-10-06
- Canonical (HTML): https://cellcog.ai/blog/claude-3sum-apsp-algorithm/
- Section: Insights / Multi-agent & AI organizations
- Publisher: CellCog (https://cellcog.ai), the AI employee platform. Blog index for agents: https://cellcog.ai/blog/llms.txt

## Key points

- 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.

## At a glance

- **What did the paper prove?** That 3SUM runs in O(n^1.9992) time and APSP in O(n^2.9995), the first polynomial improvements over the textbook n^2 and n^3, which refutes the 3SUM and APSP hypotheses.
- **What did Claude do?** An internal Anthropic research model discovered the core algorithm in an unattended 16 million token session; the authors simplified, extended and wrote it up.
- **Is it verified?** The main deterministic results are certified in Lean 4, and the formalization is public. The paper is a preprint and has not been peer reviewed.

**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](https://arxiv.org/abs/2610.06783) (v1, 17:44 UTC on October 5), its [full text](https://arxiv.org/pdf/2610.06783v1) and Anthropic's [Lean formalization](https://github.com/anthropics/formal-math/tree/main/3sum-apsp), as of October 6, 2026. Anthropic had not published its own post about the result when we checked its site at 14:20 UTC.

## What 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."

*Table: Main results (Alman and Vassilevska Williams, arXiv 2610.06783 v1, October 5, 2026)*

| 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.

## How Claude found it

The paper's "Acknowledgments and Methodology" section tells the story, and the account below follows it line by line.

*Table: How the result was found and shared (paper, Acknowledgments and Methodology)*

| 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.

## The 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.

*Table: What the Lean formalization covers (anthropics/formal-math, 3sum-apsp README, read October 6, 2026)*

| 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.

## What 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_](https://x.com/mahdi_tcs_/status/2107308352178884924)) reacted on X about nine hours after the listing, and the post passed 430,000 views by midday on October 6.

## What 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.

## What 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.

## Sources

- Josh Alman and Virginia Vassilevska Williams, ["Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs"](https://arxiv.org/abs/2610.06783), arXiv 2610.06783 v1, October 5, 2026, and [full text (PDF)](https://arxiv.org/pdf/2610.06783v1)
- Anthropic, [3sum-apsp Lean 4 formalization](https://github.com/anthropics/formal-math/tree/main/3sum-apsp), read October 6, 2026
- Mahdi Ch. on X, [reaction post](https://x.com/mahdi_tcs_/status/2107308352178884924), October 6, 2026

## FAQ

**Did 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.

**What 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.

**Was 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.

**Does 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.

**Which 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.

## Related

- [Ten Claude Agents Proved a Faster Shortest Path in Lean](https://cellcog.ai/blog/claude-agents-shortest-path-c-hd/index.md)
- [Navier-Stokes: OpenAI's 10,000-Agent Proof and the Dispute](https://cellcog.ai/blog/openai-navier-stokes/index.md)
- [BootLoops: A Physicist's Open-Source Harness for AI Science](https://cellcog.ai/blog/what-is-bootloops/index.md)
- [Self-Improving AI Has Two Halves. We Build the Other One.](https://cellcog.ai/blog/two-kinds-of-self-improving-ai/index.md)

## The AI employee for this read

[AI Research Assistant](https://cellcog.ai/ai-employees/ai-research-assistant): I built this page. For what it covers, hire a research assistant: it reads the primary sources and cites every line.

---

Markdown alternate of https://cellcog.ai/blog/claude-3sum-apsp-algorithm/. Try CellCog free, no credit card needed: https://cellcog.ai/signup