An internal research version of Claude found an algorithm that broke two longstanding barriers in computer science while working on a different problem
An internal research version of Claude found an algorithm that broke two longstanding barriers in computer science while working on a different problem
On October 5, Josh Alman (Columbia University) and Virginia Vassilevska Williams (MIT) published a preprint with a complete proof: 3SUM (determining whether any three of n numbers sum to zero) can now be solved in n^1,9992 time instead of n², and the all-pairs shortest paths problem (APSP) in n^2,9995 time instead of n³. Through established connections between problems, this refutes both original conjectures and several related ones that underpinned hundreds of conditional results in complexity theory. The paper’s main theorems were independently checked in Lean 4, a program for mechanically verifying mathematical proofs.
3SUM and APSP are simple enough to state that they are taught in first-year computer science courses. For decades, attempts to improve on the elementary solutions to either problem were unsuccessful. Fine-grained complexity theory grew out of these unsuccessful attempts: researchers adopted the impossibility of speeding up 3SUM and APSP as a working assumption and derived hundreds of conditional results of the form, “If these two problems cannot be solved faster, then neither can these others.”
Vassilevska Williams helped build much of this theory. Now, with Alman, she has published a proof that overturns a foundational assumption of the field. The changes in the exponents are barely perceptible, amounting to thousandths, yet they break the APSP barrier for the first time in sixty years (the solution method had remained unchanged since the Floyd-Warshall algorithm in 1962) and the 3SUM barrier for the first time in thirty. The result leaves SETH, the best-known conjecture in complexity theory, unaffected.
An Anthropic employee was testing an internal version of Claude on cryptographic schemes whose security depended on a graph theory conjecture that Vassilevska Williams and her coauthors had proposed several years earlier as a basis for encryption. The model was asked to check and improve these schemes. Instead, it disproved the conjecture itself, first for the average case and then for the more general worst case, in a single session with 16 million output tokens and no human involvement. Anthropic shared the finding with the authors in September under a confidentiality agreement, providing compensation and access to the public version of Claude; Alman is a former PhD student of Vassilevska Williams at MIT. They then worked through the algorithm, strengthened it, developed a complete proof, and added a section on data structures. “The authors take full responsibility for this paper,” they write, distinguishing the model’s contribution from their own.
Anthropic used the same Claude model to verify the finished paper in Lean 4. The paper’s five main claims are collected in a separate file on GitHub containing only precise statements, without any proofs. The proofs are elsewhere in the library, and a dedicated program checks that each proved theorem matches the stated claim exactly.
In 2011, Vassilevska Williams was among the first in 24 years to improve the speed record for matrix multiplication. “Nobody thought this was possible. <…> This is an absolutely incredible result,” wrote one participant in a discussion on Hacker News that drew theoretical computer scientists.
Half a year ago, the mathematician Terence Tao entrusted the Claude Code AI agent with autonomously formalizing a proof. After 45 minutes and a computer crash, it had produced no result; progress came only through a step-by-step approach with a human involved at every lemma. Here, the model worked through the authors’ entire proof without a human in the session, and the result can be checked mechanically.