3SUM Breakthrough: How Claude Broke the O(n²) Barrier and Why 1.9992 Matters

Given a list of numbers, can you find three that add up to zero? That’s the 3SUM problem. The familiar solution takes quadratic time, roughly proportional to the square of the input size. A new paper credits Claude with discovering an algorithm that pushes the exponent below two.

The headline result is a deterministic running time of \(O(n^{1.9992})\) for integers whose magnitudes are polynomially bounded. The improvement looks almost comically small. In complexity theory, however, it crosses a threshold that decades of research had failed to cross.

For readers arriving from LeetCode, this isn’t a replacement for your two-pointer solution. The breakthrough concerns deciding whether a qualifying triple exists, rather than listing every unique answer. Its significance is a new way to solve a family of problems that researchers had treated as foundations for computational hardness.

1. What Is the 3SUM Problem?

The decision problem asks whether a collection of \(n\) numbers contains three entries whose sum is zero. For example, the list [-4, -1, 0, 1, 2] has a valid triple because \(-1+0+1=0\). A decision algorithm can stop once it establishes that an answer exists.

The new paper, Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs, was posted on October 5, 2026. Its authors are Josh Alman and Virginia Vassilevska Williams.

The input restriction matters. If numbers can contain arbitrarily many digits, arithmetic itself can become expensive. The theorem includes assumptions about number size and the operations a computer can perform efficiently.

1.1. Is This the Same as 3SUM LeetCode #15?

The underlying arithmetic question is closely related, but the output requirement differs. LeetCode #15 asks for all unique triplets that sum to zero, using distinct array indices. The theoretical result concerns a yes-or-no answer.

That difference affects complexity. Some inputs have quadratically many distinct answers. An algorithm that explicitly prints them must spend time producing that output, regardless of how quickly it detects one match.

So the paper doesn’t promise a subquadratic method for returning every LeetCode triplet. For interview preparation, sorting, two pointers, and careful duplicate handling remain the relevant ideas.

2. Why the Standard Algorithm Takes Quadratic Time

Brute force tries every combination of three entries, requiring \(O(n^3)\) time. The standard improvement sorts the array, fixes one entry, and searches for the remaining pair with two pointers.

For each fixed entry, the pointers move inward through the remaining array. If the sum is too small, advance the lower pointer. If it’s too large, move the upper pointer backward. Sorting makes those moves meaningful because the values are ordered.

Each scan takes at most linear time, and there are \(n\) choices for the fixed entry. That gives \(O(n^2)\) overall. The \(O(n\log n)\) sorting cost is smaller than the quadratic scanning cost.

The challenge wasn’t that nobody had improved the textbook bound. Researchers had shaved logarithmic factors. The unresolved question was whether a fixed amount could be removed from the exponent itself.

3. What the 3SUM Hypothesis Actually Claimed

The 3SUM hypothesis was a conjecture about how difficult the decision problem must be in a specified computational model. Roughly, it claimed that no algorithm could solve it in

\(O(n^{2-\epsilon})\)

for any fixed constant \(\epsilon>0\).

This is what truly subquadratic means. A running time such as \(n^2/\log n\) is smaller than quadratic, but its advantage doesn’t equal a fixed power of \(n\). For every fixed positive exponent reduction, the logarithmic saving eventually falls behind that polynomial saving.

The new bound sets \(\epsilon=0.0008\). Small is enough. The hypothesis excluded every fixed positive value, so one qualifying algorithm refutes it.

Researchers used the conjecture to establish conditional hardness for other problems. Those arguments said, in effect, that a substantial speedup for another task would also yield a substantial speedup here. The condition was always part of the claim. It wasn’t an unconditional law of computation.

4. What Claude Actually Discovered

Claude wasn’t originally assigned to solve this classic algorithms problem. According to the methodology section, an Anthropic employee used an internal research model to investigate open questions in cryptography.

One question concerned constructions relying on the average-case hardness of Zero-\(k\)-Clique, a graph problem involving cliques whose edge weights sum to zero. Claude was asked to verify and improve the constructions. Instead, it developed a new algorithm, first for the average case and then for the worst case.

The paper reports that the session used 16 million output tokens with no human input. That describes the discovery session after its initial setup. It doesn’t mean the entire project lacked human direction or subsequent review.

Anthropic shared the algorithm with Alman and Vassilevska Williams in September 2026 under a confidentiality agreement, offered compensation, and provided access to public Claude. The authors then worked to understand and develop the result.

Their contributions included changing the presentation and numerical parameters, using established reductions, deriving a stronger data structure version, and establishing further consequences. Both authors take responsibility for the paper. Crediting the model’s discovery and the researchers’ development work gives a more accurate account than assigning the entire achievement to either side alone.

The model is described as an internal research model. The methodology doesn’t establish that public Claude can reproduce the discovery.

5. How the New Algorithm Works Without the Heavy Math

The central idea concerns thin matrix products. Imagine multiplying an \(N\)-by-\(D\) matrix by a \(D\)-by-\(N\) matrix, where \(D\) is much smaller than \(N\). The output has \(N^2\) entries, even though the shared dimension is narrow.

Now suppose you need only selected output entries. Computing the full product wastes work on answers you’ll never use. Computing each requested entry separately also wastes opportunities to share intermediate calculations.

Claude’s algorithm finds a way between those options. It modifies a version of Coppersmith’s rectangular matrix multiplication method, built from an identity due to Schönhage, to perform only the operations needed for selected outputs.

In one stated regime, \(D\leq N^{1/18}\), it computes up to \(N^2/\sqrt D\) requested entries in \(O(N^2/D^{0.063})\) operations. Those restrictions are part of the result, rather than incidental bookkeeping.

The graph interpretation makes the connection easier to see. Matrix entries can encode connections between vertices. Their products can reveal shared neighbors, which establish triangles.

The technique handles a sparse graph split into three groups, with one group much smaller than the other two. Established transformations connect this lopsided triangle problem to Exact Triangle, which asks whether three edge weights around a triangle sum to zero. Further reductions yield faster algorithms for the original arithmetic problem and shortest paths.

6. Why 1.9992 Matters More Than It Looks

The numerical improvement is tiny. If we compare only the powers of \(n\), the ratio between the quadratic baseline and the new bound is

\(\frac{n^2}{n^{1.9992}}=n^{0.0008}.\)

At a million inputs, that factor is about 1.011. At a trillion inputs, it’s about 1.022. Even extraordinary input sizes barely move the needle.

These are illustrations of growth rates, not runtime benchmarks. They ignore constants, overhead, memory behavior, and implementation details. They don’t show that the proposed algorithm would beat a standard implementation by those percentages.

The theoretical change is much larger than the numerical change. Before this result, a fixed exponent reduction was conjectured impossible. The paper provides one. A threshold either holds or it doesn’t, and an improvement of 0.0008 is enough to decide that question.

That matters because a first algorithm can expose techniques that later work improves. It also changes which conjectures researchers can safely use as assumptions. The result removes a proposed barrier, while leaving the best achievable exponent unknown.

7. Is the Algorithm Useful in Practice?

The paper offers no basis for replacing production code with this method today. Its authors explicitly describe the algorithms as algebraic and potentially impractical, with enormous constants hidden inside the big-O notation.

An asymptotic bound describes how work grows as the input becomes sufficiently large. It doesn’t identify the input size where one implementation overtakes another. A better exponent can coexist with worse performance on every dataset anyone can realistically process.

The matrix machinery and multiple reductions make implementation performance a separate research question. Without a working implementation and benchmarks, claims about faster applications would outrun the evidence.

For developers, the sensible response is to retain practical algorithms and watch for follow-up work. For researchers, there’s already something usable: a new technique, a revised understanding of hardness, and concrete targets for improving the exponent or reducing overhead.

The distinction also protects the achievement from an unfair test. A theorem about asymptotic possibility shouldn’t be judged as if it were a library release promising lower latency next week.

8. Is This Really a Matrix Multiplication Breakthrough?

Yes, the technical engine is a selected-entry algorithm for thin matrix products. Describing it as a 3SUM algorithm is also justified because the paper derives a valid faster algorithm for that problem.

The bridge is a fine-grained reduction, a transformation that connects problems while tracking how running times change. An algorithm for the target problem can become an algorithm for the source problem, provided the transformation preserves enough of the speedup.

These connections had often been used to argue that problems were hard. The same machinery now distributes an algorithmic improvement. The reductions were doing useful work all along, even when their most visible role was explaining why progress seemed unlikely.

There’s an important limit: direction matters. If solving problem B quickly would solve problem A quickly, a faster algorithm for A doesn’t automatically make B faster. The paper therefore does not supply faster algorithms for every problem previously labeled 3SUM-hard.

Some geometric and dynamic problems remain open.

9. What Changes for All Pairs Shortest Paths?

The same framework gives a deterministic \(O(n^{2.9995})\) algorithm for all pairs shortest paths on directed graphs with polynomially bounded integer weights and no negative cycles. The task is to compute the shortest-path distance between every pair of vertices.

That crosses the corresponding cubic exponent threshold, although it carries the same practical caveats.

Other consequences reported in the paper include:

• Exact Triangle: deterministic \(O(n^{2.9983})\) time with polynomially bounded integer weights.
• Real-valued 3SUM: \(O(n^{1.998})\) expected time using a Las Vegas algorithm, which always returns a correct answer but has randomized running time.
• Tree Edit Distance: \(O(n^{2.9995})\) time for polynomially bounded integer costs.
• Related problems: polynomial speedups for 3XOR and fixed-size Zero-Weight \(k\)-Clique, among others.

The real-valued result uses an abstract model with exact comparisons, additions, and subtractions. It shouldn’t be read as a benchmark for ordinary floating-point arrays, or ranked against the integer theorem without acknowledging the different assumptions.

10. What This Does Not Solve

This result does not resolve P versus NP. The headline problems already had polynomial-time algorithms. Improving a polynomial exponent is a different question from deciding whether every problem with efficiently checkable solutions can also be solved efficiently.

The paper also leaves the Strong Exponential Time Hypothesis, or SETH, unaffected. Its techniques don’t establish the corresponding breakthrough for Orthogonal Vectors.

Nor does the result provide the sought fixed-exponent improvements for general \(k\)-SUM or \(k\)-XOR when \(k\geq4\). The 3SUM-Indexing conjecture, concerning preprocessing and later queries, remains unaffected too.

These limitations reveal the structure of the discovery. The algorithm exploits particular relationships among arithmetic, selected matrix entries, and triangle problems. It doesn’t offer a universal shortcut for computational difficulty.

11. How the Result Was Checked

The verification story has two layers. First, the human authors examined the discovered algorithm, simplified and strengthened it, derived consequences, and wrote the paper. They explicitly accept responsibility for its contents.

Second, after the paper was completed, Anthropic used an internal research model to formalize major results in Lean 4 with Mathlib. The methodology reports formalizations of the integer decision bound, Exact Triangle, shortest-path and matrix-product results, and the Zero-Weight clique result. It also reports formalizing the supporting lemmas and prior results those statements require.

A proof assistant checks formal derivations against precisely stated definitions and assumptions. That provides a different kind of assurance from asking another language model whether an argument sounds convincing.

Still, formal certification and independent review aren’t interchangeable. Anthropic organized the formalization, and the paper is a newly posted preprint. Readers should distinguish the authors’ mathematical review, the reported machine-checkable proofs, and any later external scrutiny.

12. Where the Next Breakthrough Could Come From

The authors identify room to improve the exponents. Their reductions lose portions of the underlying speedup, so better transformations could preserve more of it. They also describe ways to obtain slightly better bounds than the headline presentation.

A stronger selected-entry matrix algorithm could propagate further gains across the same network. More practical methods remain an open direction, as do techniques that work when the graph’s smaller group is less severely restricted.

None of that guarantees a dramatic next step. The useful change is that researchers now have an algorithmic foothold where a conjectured barrier once stood.

Claude’s 3SUM discovery hasn’t made everyday code dramatically faster. It has shown that a foundational exponent threshold can be crossed, and that decades of work connecting problems can turn one new idea into many results.

Follow Binary Verse AI for research breakdowns that connect the headline, the proof, and the practical consequences. When the next exponent falls, the question will be how much of that progress survives the journey into usable software.