Claude found the algorithm that broke two famous computer science hypotheses

Two of the most trusted assumptions in theoretical computer science just fell, and the algorithm that knocked them over was found by an AI. In a paper posted to arXiv on Monday, October 5, the computer scientists Josh Alman of Columbia University and Virginia Vassilevska Williams of MIT present the first truly faster algorithms for two textbook problems called 3SUM and All Pairs Shortest Paths. In the paper itself, they write that Claude, an AI model developed by Anthropic, discovered the algorithm at the core of the result.

That sentence is the reason this story is spreading so fast. AI systems have helped with math before, mostly by checking known results or by finishing proofs that experts already expected to be true. This is different. Here, an internal research model was working on something else, ran into a problem that a whole field had treated as practically settled, and came back with a method that proves the field's working assumption wrong.

The three things you need to know

• What happened. The paper gives a deterministic algorithm for 3SUM on n integers that runs in O(n^1.9992) time, and one for All Pairs Shortest Paths on directed graphs with integer weights that runs in O(n^2.9995) time. Both beat the classic textbook bounds of n squared and n cubed by a real power of n, not just by a small logarithmic factor. That is enough to refute the 3SUM hypothesis and the APSP hypothesis of fine grained complexity theory.
• How it happened. According to the paper's section on methodology, an Anthropic employee used an internal research model to look at open problems in cryptography, specifically constructions that rely on a problem called Zero Weight k Clique being hard on average. Claude was asked to verify and improve those constructions. Instead, it developed this algorithm, first for the average case and then for the worst case. The session used 16 million output tokens with no human input.
• Is it real. The two authors are leading researchers in exactly this area. They simplified, strengthened and extended the algorithm and wrote the paper. After the paper was finished, Anthropic used an internal model to certify the main theorems in the Lean 4 proof assistant with the Mathlib library, and the formal proofs are public on GitHub. The paper is still a preprint and has not gone through peer review yet.

What 3SUM and APSP actually are

The two problems sound abstract, but they are easy to state. In 3SUM you get a list of n numbers and you have to decide whether any three of them add up to zero. The obvious method checks pairs in a clever order and needs about n squared steps. That method is taught in basic algorithms courses, and for decades nobody could do much better. Earlier improvements only shaved off small logarithmic factors, which is a bit like saving a few seconds on a marathon.

All Pairs Shortest Paths, usually shortened to APSP, asks for the shortest route between every pair of points in a weighted network. Think of a road map where every road has a length, and you want a full table of distances from every town to every other town. The classic answers, the Floyd and Warshall algorithm from 1962 and Johnson's algorithm from 1977, need about n cubed steps for n points. The best previous improvement, by Ryan Williams in 2018, only removed a factor that grows slower than any power of n.

Because both problems resisted so many attempts, researchers turned the frustration into a theory. Fine grained complexity assumes that 3SUM really needs about n squared time and that APSP really needs about n cubed time. From those two assumptions, plus a third one about Boolean satisfiability, the field built a large web of reductions. A reduction says: if you could solve problem B fast, you could also solve problem A fast. So if A is believed to be hard, B must be hard too. Many problems in computational geometry, string matching and dynamic graphs got their "probably optimal" label this way.

Why tiny exponents are a big deal

At first glance, going from n^2 to n^1.9992 looks like nothing. For any input you could store on a real computer, the textbook method will still win, and the authors say openly that their new algorithms are algebraic, that the hidden constants are enormous and that the methods are potentially impractical in their current form. Nobody will rewrite a route planner or a database engine tomorrow because of this paper.

But the hypotheses were never about practical speed. They were about whether any polynomial improvement exists at all. Saying "3SUM needs n^(2 minus o(1)) time" means no algorithm can save even a tiny fixed power of n. One working counterexample is enough to break that claim, and this paper provides it. Once the base assumption falls, the conditional lower bounds that were proven from it no longer give evidence of hardness. In the paper's own words, the authors view this as a great success for fine grained complexity, because the web of reductions that was meant to show hardness now turns one new algorithm into faster algorithms for a long list of problems at once.

That list is long. Through known reductions, the paper also refutes the real valued versions of the 3SUM and APSP hypotheses, the Exact Triangle hypothesis, the Zero Weight k Clique hypotheses, and three conjectures about hinted online matrix vector multiplication. It gives the first truly subcubic algorithms for problems such as Negative Triangle, Minimum Weight Cycle, Radius, Median, Replacement Paths and Tree Edit Distance with integer costs, and the first truly subquadratic algorithms for many problems in the 3SUM class. It even beats an algorithm by Uri Zwick for shortest paths in unweighted directed graphs that had not been improved for more than two decades, other than through faster matrix multiplication.

How the algorithm works, in plain words

Everything in the paper flows from one new tool for multiplying matrices. Imagine two very thin matrices, one tall and narrow and one short and wide. Multiplying them produces a huge square result, and writing down every entry of that result already takes a lot of time. The new idea is that many problems only need a small, scattered set of entries from that result, not the whole thing.

The algorithm starts from a classic fast matrix multiplication method by Don Coppersmith, which is built on a ten multiplication identity found by Arnold Schönhage in 1981. Like the famous Strassen algorithm, it works recursively, splitting the problem into smaller pieces again and again. The trick is to walk only the branches of that recursion tree that actually lead to the wanted entries and to skip everything else. The paper then proves that, thanks to special sparsity properties of Schönhage's identity, the number of branches you need is polynomially smaller than the full tree.

In graph language, this solves a problem called All Edges Sparse Triangle on lopsided graphs, where two groups of nodes are large and the third group is very small. Earlier work had already shown that Exact Triangle, and through it 3SUM and APSP, can be reduced to exactly this lopsided case. So the chain was there, waiting for someone to make its last link fast. Interestingly, the authors note that they themselves had tried similar approaches with other matrix multiplication identities before, without success.

What Claude did and what the humans did

The paper is unusually transparent about who did what, and that matters for judging the claim. According to the methodology section, the core algorithm that refutes the 3SUM, APSP and Exact Triangle hypotheses came from Claude. Anthropic shared it with Alman and Vassilevska Williams in September 2026 under a confidentiality agreement, offered compensation, and gave them access to the public version of Claude. What the authors received was essentially the algorithm in Section 2 of the paper, but presented differently and with other numbers.

The two researchers then did the work that turns a raw discovery into a solid paper. They used the known reductions to connect the algorithm to all the other problems, which they say both suffices and strengthens the link. They derived the data structure version of the method and its connection to the hinted matrix vector conjectures. They also write that, together with Claude, they found some algorithms with slightly better exponents that are much more complicated, and that they deliberately left those out to keep the presentation simple. Finally, they state that they used Claude to help with writing, figures and checking mathematical details, and that they take full responsibility for the content.

Why the Lean proofs matter

A claim this big naturally invites doubt. That is where Lean comes in. Lean is a proof assistant, a program that checks every single logical step of a proof against a small trusted core. If a formal proof compiles in Lean, a mistake in the argument is extremely unlikely. According to the paper, Anthropic used an internal research model to formalize the main results after the paper was written: the Exact Triangle algorithm, the 3SUM algorithm, the APSP and min plus product algorithm, and the Zero Weight k Clique case. All lemmas and earlier results those statements depend on are formalized too, and the code sits in the public anthropics/formal-math repository.

Not everything is formalized. The randomized algorithms for real valued inputs and some running time calculations are outside the Lean project. Still, the combination of two respected experts signing the paper and a machine checked proof of the central theorems is a much stronger foundation than most fresh preprints have. Peer review will add a further check in the coming months.

Why it matters

• A new kind of AI contribution. This is not an AI confirming something experts already believed. It is an AI breaking a widely held conjecture in a core field of computer science, while it was asked to do something else.
• Science gets faster checks. The pairing of an AI discovery with a formal Lean proof shows a workflow that other fields can copy: let models search, then let proof checkers and human experts verify.
• Cryptography should pay attention. The discovery came from a model probing cryptographic constructions that assume certain problems are hard on average. If such assumptions can fall to an automated search, designers will want to test their foundations against AI before attackers do.
• Theory needs to be rebuilt. Many papers rested their hardness results on 3SUM and APSP. Those results do not become wrong, but their message changes, and researchers will have to find new reasons, or new algorithms, for the problems involved.

What is still open

Plenty. The speedups are small and far from practical, and the method needs one side of the graph to be very small, so the balanced version of the sparse triangle problem is still open. The Strong Exponential Time Hypothesis, the Orthogonal Vectors problem and k SUM for k of four or more are not affected, and the authors explain why their technique does not seem to reach them. It is also open whether the method can be pushed further, or turned into something combinatorial and practical. And beyond the paper, Anthropic has not yet explained in detail how the internal model was set up, so outside researchers cannot yet reproduce the discovery process itself.

Dany's take

I read a lot of AI news every day, and most "AI makes breakthrough" headlines fall apart after two paragraphs. This one does the opposite. The deeper you read, the more careful it looks: two top experts in the exact field, a clear split of who did what, honest words about how impractical the algorithm still is, and a public Lean proof anyone can check. What stays with me is the detail that Claude was not even asked to attack 3SUM. It was supposed to check some crypto constructions and found a crack in the ground they were standing on. That is exactly the kind of surprise we used to expect only from very good human researchers. My guess: in a year, "found by an AI, checked in Lean, written up by humans" will be a normal line in serious papers. The question for all of us is how fast the rest of science learns that workflow.

Source

The paper "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs" by Josh Alman and Virginia Vassilevska Williams is available on arXiv. The Lean formalization is in the anthropics/formal-math repository on GitHub.