Lopsided Triangles

3SUM asks whether some three of n given numbers add up to zero. The textbook answer sorts the numbers, then, for each number in turn, walks two pointers inward from the ends of the rest of the list. If the three numbers sum to less than zero, the left pointer moves right; if more, the right pointer moves left. That is about n²/2 steps.

All-pairs shortest paths (APSP) asks for the distance between every pair of vertices in a graph with weighted edges. Floyd and Warshall's triple loop takes n³ steps on n vertices.

Decades of work shaved these bounds only by factors that grow slower than any power of n: logarithms for 3SUM, and a factor of 2^{Ω(√log n)} for APSP. Fine-grained complexity turned the failure into two hypotheses.

• The 3SUM hypothesis. 3SUM on n integers of polynomial size needs n^2−o(1) time.
• The APSP hypothesis. APSP with polynomially bounded integer weights needs n^3−o(1) time.

The o(1) in the exponent lets through any speedup whose effect on the exponent fades to nothing, such as dividing by a logarithm. What the hypotheses rule out is a truly subquadratic algorithm, one that runs in n^2−δ time for a fixed δ > 0. The new paper gives one, with δ = 0.0008.

In practice that exponent buys nothing. The factor n^0.0008 reaches 2 only when n has 377 digits, and the constant factors the algorithm hides are enormous. The result matters because the hypotheses were claims about exponents, and a great deal of theory was built on them.

Fine-grained complexity connects problems by reductions. A reduction from problem A to problem B is an algorithm for A that calls a solver for B, with overheads small enough that a polynomially faster algorithm for B gives one for A. Read in one direction, a reduction moves hardness: if A is hard, B must be hard too. Read in the other, it moves speed.

Over the years the field tied dozens of problems to 3SUM and APSP this way. Both of them reduce to Exact Triangle: does a weighted tripartite graph contain a triangle whose three weights sum to zero? Exact Triangle reduces in turn to a question about triangles in an unweighted graph that is sparse and lopsided. That question sits at the bottom of the web, so a faster algorithm for it speeds up everything above.

The problem at the bottom is Lopsided All-Edges Sparse Triangle. Take a graph with three parts: two big parts A and B of n vertices each, and a small middle part of D vertices, where D = n^ε for some small ε. You are given a set W of query pairs (a, b). For each one, decide whether a and b have a common neighbour in the middle, which would close a triangle through the edge a–b.

In matrix terms, let X be the n×D 0/1 matrix of edges between A and the middle, and Y the D×n matrix of edges between the middle and B. The entry (XY)[a, b] counts the common neighbours of a and b. So the task is to compute the entries of the product XY at the positions in W, the wanted entries. With D far smaller than n, the matrices are thin.

There were two ways to do this. Compute each wanted entry as an inner product of length D, for |W|·D operations. Or compute the whole product with fast rectangular matrix multiplication, about n² operations whether or not you want all of it. The reductions produce instances with about n²/√D query pairs, where the first way costs n²√D. Either way you pay at least one operation per entry of the product.

The new algorithm pays n²/D^0.063, fewer operations than there are entries in a product it never writes down. This holds whenever D ≤ n^1/18, and with smaller savings up to about D = n^0.12.

Exact Triangle has weights on its edges. The lopsided problem has none. The reduction between them removes the weights by working modulo a prime p of about √D.

A triangle a, b, c has weight S = w(a,b) + w(b,c) + w(a,c). Group the query pairs by ρ = w(a,b) mod p. Make a middle vertex (c, σ) for each vertex c on the third side and each residue σ < p. Join a to (c, w(a,c) + ρ) and b to (c, −w(b,c)), both mod p. Then a and b share the neighbour (c, σ) exactly when S(a,b,c) ≡ 0 (mod p). Each of a and b has one edge per c, so for each c the question is whether their edges land on the same residue.

Every zero triangle shows up as a shared neighbour, and so do some false positives: triangles whose weight is a nonzero multiple of p. The reduction checks each candidate exactly. To keep false positives rare without randomness, it counts them for every prime between √D/2 and √D (one matrix product with polynomial entries per prime) and uses the prime with the fewest. The middle part has one vertex per pair (c, σ), so the third side is cut into pieces of at most √D vertices, each with its own instances, to keep the middle part within D.

The new algorithm is a fast matrix multiplication algorithm with most of its work skipped. Its skeleton is Strassen's from 1969, which multiplies two 2×2 matrices with seven multiplications instead of eight:

For N×N matrices, cut each into 2×2 blocks and apply the identity to the blocks, recursing on each of the seven block products. After L = log₂N levels the tree has 7^L = N^2.81 leaves, and each leaf multiplies two numbers. Two facts carry over to everything below. The multiplications happen only at the leaves. And the encoding of A depends only on A, the encoding of B only on B.

The new algorithm replaces Strassen's identity with one Arnold Schönhage found in 1981. It computes two unrelated things at once. The outer product of (x₁, x₂, x₃) and (y₁, y₂, y₃) is the nine numbers x_iy_j. The inner product of four p's and four q's is the one number Σ p_ijq_ij. Separately they take 9 + 4 = 13 multiplications. Schönhage needs ten.

Pad the p's into a 3×3 matrix p̂ whose columns sum to zero, and the q's into q̂ whose rows sum to zero. The ten products are

P_ij = (x_i + p̂_ij)(y_j + q̂_ij) for i, j = 1, 2, 3 P₀ = −(x₁ + x₂ + x₃)(y₁ + y₂ + y₃)

and the outputs are z_ij = P_ij for the outer product and z₀ = P₀ + Σ P_ij for the inner product. Change any input and watch:

The inner product comes out exact. The x_iy_j terms cancel against P₀, and the cross terms vanish because of the zero sums. The outer product comes out with an error: z_ij carries x_iq̂_ij + p̂_ijy_j + p̂_ijq̂_ij. Every error term multiplies at least one inner-product input, a p or a q, into an outer-product output. That is what will make the error harmless.

One more property, and it is the one the new algorithm lives on. Only one product, P_ij, feeds the output z_ij. All ten feed z₀.

Use the identity recursively for L levels, as Strassen did. The inputs become arrays indexed by strings of L variables, one per level. A left string such as x1 p11 x2 x3 p22 x1 picks a left variable at each level; an output string such as z13 z0 z21 z33 z0 z12 picks an output variable at each level. The leaves are strings of L products, 10^L of them.

Each level can serve the outer product or the inner one. Fix a set Q of m levels to serve the inner product. The left strings with p's exactly on Q are the entries of an N₀×D matrix X_Q: the x's elsewhere pick one of N₀ = 3^L−m rows and the p's on Q pick one of D = 4^m columns. The right strings form a D×N₀ matrix Y_Q, and the output strings with z₀ exactly on Q are the entries of the product X_QY_Q.

Now set every input string whose inner set does not have exactly m elements to zero. To feed an output with z₀ on the levels of Q, an input string needs a p (or a q) on each of them, which uses up all m of its inner variables. Everywhere else it has an x (or a y). The error terms need an inner variable at a level where the output has some z_ij, so they never appear (Lemma 9), and one run of the recursion computes all K = Lm products X_QY_Q at once, each independent of the others. With m much smaller than L they are thin: D is tiny next to N₀.

To multiply a large thin X by Y, cut X into row blocks and Y into column blocks of N₀, and give each block product its own set Q. A square tile of up to K block products is one run of the recursion. The rest of this page uses L = 6 and m = 2: fifteen sets Q, nine of them used by a 3×3 tile of 81×16 by 16×81 block products.

Which leaves does one entry need? The decoding sends P_ij only to z_ij and z₀. So an output string w is fed by exactly the leaves that choose P_ij wherever w has z_ij, and any of the ten products on the m levels where w has z₀. That is 10^m leaves: 100 here, for an entry that is an inner product of length 16. In general 10^m = D^1.66, worse than computing the entry directly.

What rescues it is sharing. Sort the leaves under w by their order: the number of levels of Q at which they choose one of the nine P_ij instead of P₀. The leaf of order 0 chooses P₀ everywhere on Q. It is the private leaf of w, and no other entry uses it. A leaf of order d is shared by L−m+dd entries, one in each product whose set Q contains the levels where the leaf chose P₀.

Under each entry there are α_d = md·9^d leaves of order d: 1, 18 and 81 here. High orders are numerous under each entry but shared widely. Low orders are few but nearly private. Across the whole tile there are β_d = Lm−d·9^L−m+d leaves of order d. When L is large next to m (the paper takes L = 19m), each step up in order more than halves that count: β_d ≤ 2^−dM, where M is the number of entries in the tile.

The new algorithm makes two changes to the plain recursion. First, it computes the encodings once: the number each leaf multiplies depends on X alone or on Y alone, so each band of blocks is encoded once and shared by every tile it touches. Second, it runs the recursion pruned. Each call receives the set of wanted outputs below it and makes a child call only if that child feeds one of them. By Lemma 10 the pruned recursion visits exactly the leaves that feed some wanted entry, and visits each of them once, however many entries share it.

Below is a real instance: a lopsided graph with 243 + 16 + 243 vertices, so X is 243×16 and Y is 16×243, multiplied as one tile with L = 6 and m = 2. Pick query pairs and run it. Your browser computes both encodings (a million numbers each), runs the pruned recursion, and checks every answer against a direct count of common neighbours.

At this size the pruning does not pay. Six levels are too few for sharing to beat a hundred leaves per entry, and the 16-term inner products would be cheaper done directly. The saving appears only when L is many times m and m is large, at sizes nobody will ever run. The count, though, can be done at any size.

Lemma 11 bounds the leaves a wanted set U needs, order by order. There are at most |U|·α_d of order d (charge each wanted entry for its own) and at most β_d (take every leaf of that order). Take the smaller at each order and add. Low orders are cheap to charge; high orders are cheap to take whole.

With L = 19m and |U| = M/√D, the density the reductions produce, the total sits below M by a factor that grows like a power of D. The paper proves a factor of D^1/18 with a deliberately simple estimate, splitting at order m/9; the exact minimum plotted here does a little better. Shrink L toward 10m and the falling curve flattens at the start: the low orders each hold nearly M leaves, and the saving all but disappears. The ratio L/m also sets how thin the product must be: the encodings cost 10^L per band, which fits the budget only when N is a large enough power of D. That trade-off is why the technique stops near D = N^0.12.

Adding it up (Theorem 5): the encodings cost O(10^L) per band, the pruned recursion O(L²) per leaf it visits, and the total for any N²/√D wanted entries is O(N² log²D / D^1/18). Turning the same counts into a data structure, which adds up the high-order leaves into precomputed boxes ahead of time, improves the saving to D^0.063 and answers single entries not known in advance in O(D^0.437) time.

The saving then climbs the reductions, and each reduction keeps only part of it. They were designed to prove hardness, where any polynomial saving was enough.

Exact Triangle balances the number of instances against the cost of checking candidates, which keeps half of the matrix saving: O(n^3−0.00175 log n). 3SUM reduces to about √n Exact Triangle instances on √n vertices, keeping half again: O(n^1.9992). APSP and the (min,+)-product go through Exact Triangle on n^1/3 vertices and keep a third: Õ(n^3−0.00058) ≤ O(n^2.99942).

The authors note gains they left out to keep the paper simple, such as solving the all-edges version of Exact Triangle directly so that APSP keeps all of its saving instead of a third. Now that these reductions are being used as algorithms, how much of a saving they keep has become a research question of its own.

The paper's methodology section records the history. An Anthropic employee was using an internal research model on open problems in the theory of cryptography. One problem was about cryptographic constructions based on the average-case hardness of Zero-k-Clique. Claude was asked to verify and improve those constructions, and instead 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.

Found

by Claude, in a single unattended session of 16M output tokens

Shared

with the authors in September 2026, under a confidentiality agreement

As shared

essentially the algorithm of §2, with other parameters and a different reduction from Exact Triangle

Added by the authors

the known reductions used instead, the data structure of §4, Hinted OMv, many further consequences

Checked

main theorems formalized in Lean 4 with Mathlib, with every lemma and prior result they rely on

After the paper was written, Anthropic used an internal research model to formalize its main results in the Lean 4 proof assistant: Exact Triangle in O(n^2.9983), 3SUM in O(n^1.9992), APSP and the (min,+)-product in O(n^2.99942), and Zero-Weight k-Clique. The formalization is public at anthropics/formal-math. The authors state that they take full responsibility for the paper.

Not everything fell. The Strong Exponential Time Hypothesis and Orthogonal Vectors are untouched, since neither is known to reduce to a triangle problem. So are k-SUM for k ≥ 4, 3SUM-Indexing, and OMv without hints. The balanced version of All-Edges Sparse Triangle, conjectured to need m^4/3−o(1) time on graphs with m edges, is not sped up either, and the authors suggest it as a replacement hypothesis. Problems that were only known to be 3SUM-hard, such as deciding whether n points in the plane include three on a line, get no faster algorithm; for them the question is simply open again.

The authors read the result as a success for fine-grained complexity. The web of reductions was built to explain why problems were hard, and it is exactly what let one new algorithm speed up dozens of them at once.