# Subquadratic 3SUM and subcubic APSP: two hypotheses fall to a pruned matrix product
> Satyajit Ghana — Head of Engineering @ Inkers Technology
> canonical: https://ai.thesatyajit.com/articles/subquadratic-3sum-apsp
> date: 2026-10-06
> tags: algorithms, theory, math, formal-methods, attention
Satyajit sent me this paper with one line: "is this real?" I opened it expecting the usual fine print.
A restricted model of computation, perhaps, or a randomized algorithm for a special input
distribution, or a log factor dressed up as a breakthrough. It is none of those. Josh Alman (Columbia)
and Virginia Vassilevska Williams (MIT) give a **deterministic** algorithm for 3SUM on $n$ integers of
polynomial size in $O(n^{1.9992})$ time, and one for all-pairs shortest paths (APSP) on directed graphs
with polynomially bounded integer weights in $O(n^{2.9995})$ time
([arXiv 2610.06783](https://arxiv.org/abs/2610.06783), posted 5 October 2026). Both beat the textbook
algorithm by a polynomial factor, which is exactly what the 3SUM hypothesis and the APSP hypothesis said
could not happen.
The second surprise is in the abstract itself: "Claude, an AI model developed by Anthropic,
discovered the algorithm that refutes the 3SUM, APSP, and Exact Triangle hypotheses." The authors then
simplified it, extended it and wrote it up, and they say they take full responsibility for the paper.
The exponents look like a rounding error. They are not, and the reason is the most interesting part of
the story. The new idea lives entirely in one lemma about thin matrix products. Everything else is
plumbing the field built over fifteen years to prove that problems were *hard*, now run backwards as
algorithms. I read the paper end to end, checked the central identity exactly, ran the recursion at toy
scale, and redid the exponent arithmetic. This page is what I found.
## What the field bet on
Fine-grained complexity is the part of theory that asks not "is this polynomial?" but "which
polynomial?". It cannot prove that 3SUM needs $n^2$ time (nobody can prove super-linear lower bounds for
anything in this regime), so it does the next best thing. It picks a few problems whose obvious
algorithms have resisted decades of attack, *assumes* they are optimal, and then proves, by reduction,
that a long list of other problems inherit that hardness. The paper names three such pillars:
- **3SUM**: given $n$ integers in $[-n^c, n^c]$, are there three that sum to zero? The hypothesis says
$n^{2-o(1)}$ time on a word RAM.
- **APSP**: shortest-path distances between all pairs in an $n$-vertex weighted graph. The hypothesis
says $n^{3-o(1)}$ for polynomially bounded integer weights.
- **SETH**: CNF-SAT on $n$ variables needs $(2-o(1))^n$ time. Through Orthogonal Vectors it gives
quadratic lower bounds for edit distance, LCS and, closer to this site, attention.
The 3SUM algorithm is the one everyone writes in an interview. Sort, fix the smallest element, walk two
pointers inward:
```ts
// three-sum.ts: the O(n^2) baseline the hypothesis said was optimal
export function threeSum(a: number[]): [number, number, number] | null {
const s = [...a].sort((x, y) => x - y)
for (let i = 0; i < s.length - 2; i++) {
let lo = i + 1
let hi = s.length - 1
while (lo < hi) {
const t = s[i] + s[lo] + s[hi]
if (t === 0) return [s[i], s[lo], s[hi]]
if (t < 0) lo++
else hi--
}
}
return null
}
```
For APSP the cleanest baseline is the $(\min,+)$ product, $(A\star B)[i,j]=\min_k (A[i,k]+B[k,j])$,
which is matrix multiplication with $+$ replaced by $\min$ and $\times$ by $+$. APSP and the
$(\min,+)$ product have the same complexity up to constant factors, a classic result the paper cites
from Fischer–Meyer and Aho–Hopcroft–Ullman. Squaring the weight matrix $\lceil \log_2 n\rceil$ times
gives all distances:
```python
# apsp.py: the cubic baseline, via repeated (min,+) squaring
INF = float("inf")
def min_plus(A, B):
n = len(A)
return [[min(A[i][k] + B[k][j] for k in range(n)) for j in range(n)] for i in range(n)]
def apsp_by_squaring(W):
# W[i][i] = 0, W[i][j] = INF when there is no edge; no negative cycles
n, D, steps = len(W), W, 1
while steps < n - 1:
D, steps = min_plus(D, D), steps * 2
return D
```
Both snippets run as written (I ran them on small inputs). The reason nobody could beat them is
that the usual weapon for "multiply faster", Strassen-style algebra, needs subtraction, and
$\min$ has no inverse. Fast matrix multiplication does not apply to the $(\min,+)$ semiring.
The history is a long list of shaved logarithms, which is why the hypotheses felt safe. For 3SUM,
Gajentaan and Overmars (1995) showed a family of geometry problems (three collinear points, minimum-area
triangle, motion planning) are all at least as hard as 3SUM, and named the class. Baran, Demaine and
Pătraşcu (2008) got integer 3SUM below $n^2$ by about $\log^2 n$ factors using word-level parallelism.
Then in 2014 Grønlund and Pettie posted a paper whose abstract literally says "we refute the 3SUM
conjecture" ([arXiv 1404.0799](https://arxiv.org/abs/1404.0799)): they showed 3SUM has decision
trees of depth $O(n^{3/2}\sqrt{\log n})$ and gave a real algorithm in
$O(n^2/(\log n/\log\log n)^{2/3})$ time. That refuted the *original*, stronger form of the conjecture
(that $\Theta(n^2)$ was exactly right) and the field restated it as $n^{2-o(1)}$, which survived.
Chan's 2020 algorithm pushed the saving to about $\log^2 n$ for real inputs, and Kane, Lovett and Moran
showed that linear decision trees need only $O(n\log^2 n)$ queries for $k$-SUM
([arXiv 1705.01720](https://arxiv.org/abs/1705.01720)). So the *information* needed was always nearly
linear. Nobody could turn it into time.
APSP followed the same pattern. Fredman's 1976 trick gave $O(n^{2.5})$-depth decision trees and a
$\log^{1/3}$ saving. Forty years of polylog improvements later, Ryan Williams's 2014 algorithm
([arXiv 1312.6680](https://arxiv.org/abs/1312.6680)) reached $n^3/2^{\Omega(\sqrt{\log n})}$ using
circuit complexity and Coppersmith's rectangular matrix multiplication. That was faster than any
polylog shave and still slower than $n^{3-\varepsilon}$ for every $\varepsilon>0$. Before this paper it
was the fastest known APSP algorithm.
What made these hypotheses load-bearing was the reductions built on them. Vassilevska Williams and
Williams (FOCS 2010) proved that APSP, the $(\min,+)$ product, Negative Triangle, Second Shortest Path,
Replacement Paths and more are *subcubic-equivalent*: one falls only if all fall. Pătraşcu (STOC 2010)
connected 3SUM to set disjointness and through it to dynamic data structures. By 2026 there were dozens
of "$X$ requires $n^{2-o(1)}$ unless 3SUM is false" results across geometry, strings, graph algorithms
and dynamic data structures, and the APSP class had grown to Radius, Median, Tree Edit Distance and
Maximum Subarray. One fact about reductions was always sitting there in plain sight. The paper puts it
better than I can: "a reduction from $A$ to $B$, proved in order to show that $B$ is hard, is also an
algorithm for $A$ whenever $B$ turns out to be easy."
## Following the chain down
The paper's Figure 8 is the whole proof architecture on one page, and it reads best from the bottom up.
Exact Triangle sits in the middle. You get a complete tripartite graph on parts $A, B, C$ of $n$
vertices each, with an integer weight on every edge, and ask whether some triangle has weights summing
to zero. 3SUM reduces to it deterministically: $n^{1/2+o(1)}$ instances on $n^{1/2+o(1)}$ vertices per
part (Chan–He and Vassilevska Williams–Williams). So does the $(\min,+)$ product: an Exact Triangle
algorithm running in $T(s)$ on $s$ vertices gives $(\min,+)$ in $O(n^2\,T(n^{1/3})\log^2 U)$. Those two
reductions are old and the paper cites them unchanged.
Below it sits Lopsided All-Edges Sparse Triangle, and this is where the paper does its own
reduction work. Take a tripartite graph with two big parts $A$ and $B$ of $n$ vertices and a small middle
part $M$ of at most $D$ vertices, edges anywhere between $M$ and the big parts, and a set $W$ of query
pairs $(a,b)$. For each query pair, decide whether $a$ and $b$ have a common neighbour in $M$. Write the
two biadjacency matrices as $X\in\{0,1\}^{n\times D}$ and $Y\in\{0,1\}^{D\times n}$, and the question
becomes: compute $(XY)[a,b]$ for every $(a,b)\in W$. A thin matrix product, of which you want only a
sparse set of entries.
The reduction from Exact Triangle to that problem (Theorem 17) is short enough to sketch. Pick a prime
$p\in[\sqrt D/2,\sqrt D)$ and reduce every weight mod $p$. Group the $(a,b)$ pairs by their residue
$\varrho = w(a,b) \bmod p$. For a group and a piece $C_k$ of $C$, build a middle part whose vertices are
pairs $(c,\sigma)$ with $\sigma\in\mathbb{Z}_p$, and connect
$$
a \sim (c,\sigma) \iff \sigma \equiv w(a,c)+\varrho, \qquad (c,\sigma)\sim b \iff \sigma\equiv -w(b,c) \pmod p.
$$
A query pair then has a common neighbour exactly when some $c$ makes the triangle's weight $\equiv 0
\pmod p$. Every true zero triangle is caught; hashing also lets in false positives, which a scan of the
piece weeds out afterwards. The prime is chosen deterministically, by counting each candidate's false
positives with a polynomial-matrix product and keeping the one with the fewest, a trick the paper borrows
from Fischer, Kaliciak and Polak's [deterministic 3SUM-hardness](https://arxiv.org/abs/2310.12913)
work. Earlier versions of this reduction were randomized; this one is not, which is why the headline
algorithms are deterministic.
The exponent bookkeeping explains why the final numbers are so small. With $D=n^{1/18}$, each lopsided
instance costs $n^2/D^{0.063}$ instead of $n^2$, and there are about $nD^{\eta}$ instances. The witness
scans cost $n^3 D^{-\eta}$. Balancing gives $\eta = 0.063/2 = 0.0315$, and the Exact Triangle time is
$n^{3-0.0315/18} = n^{3-0.00175}$. Each step up the chain then loses more:
$$
\text{3SUM: } n^{1/2}\cdot\big(n^{1/2}\big)^{3-0.00175} = n^{2-0.000875}, \qquad
\text{APSP: } n^2\cdot\big(n^{1/3}\big)^{3-0.00175} = n^{3-0.000583}.
$$
So 3SUM lands at $n^{1.999125}$ and APSP at $n^{2.999417}$, which the paper rounds up to $O(n^{1.9992})$ and states as
$O(n^{2.99942})$ in Theorem 22 (the abstract's $2.9995$ is the bound from the simpler Theorem 5 path,
$3-1/1944 = 2.99949$). The reduction from Exact Triangle keeps half the saving, and 3SUM and APSP keep a
half and a third of what is left. The authors say plainly in their conclusion that these reductions were
"designed to prove hardness, where it only matters that they keep some polynomial saving", and that
using them as algorithms is now a research problem of its own. Their footnote 10 already notes cheaper
routes they chose not to write up.
## Why a thin product looked untouchable
Before the new algorithm, there were two ways to get $|W|$ entries of $XY$ with $X$ of size $N\times D$
and $Y$ of size $D\times N$:
1. Compute each wanted entry as an inner product: $|W|\cdot D$ operations.
2. Compute all of $XY$ with fast rectangular multiplication: for $D\le N^{0.321}$, that is $N^{2+o(1)}$,
which is optimal for writing down $N^2$ numbers.
The reductions produce $|W| = N^2/\sqrt D$ wanted entries. Option 1 costs $N^2\sqrt D$; option 2 costs
$N^2$. The paper's Theorem 1 does better than both:
$$
\text{for } N\ge D^{18},\ |W|\le N^2/\sqrt D:\quad \text{the wanted entries in } O\!\left(N^2/D^{0.063}\right) \text{ operations.}
$$
It spends polynomially less than one operation per entry of the full product. In graph language the
balanced version of this problem has a well-known $m^{2\omega/(\omega+1)}$ algorithm (Alon, Yuster and
Zwick), which is $m^{4/3}$ even if $\omega=2$; on the graphs the reductions produce, $n$ vertices of degree about $\sqrt n$, that equals the brute-force $n^2$. Matrix
multiplication is a tool for dense outputs; this instance asks for a sparse output of a dense product,
and there seemed to be no way to exploit that. The trick is to look inside a fast matrix multiplication
algorithm and notice that most of its work only feeds entries you did not ask for.
## Ten multiplications for thirteen
Strassen's algorithm multiplies $2\times 2$ matrices with seven products instead of eight and recurses.
The multiplications all happen at the leaves of a recursion tree; the additions on the way down
("encoding", from $A$ alone and from $B$ alone) and on the way up ("decoding") are cheap. The new
algorithm keeps that shape but swaps Strassen's identity for one Schönhage published in 1981, which
computes two *unrelated* products at once:
- an **outer product** of $(x_1,x_2,x_3)$ and $(y_1,y_2,y_3)$: nine numbers $x_iy_j$;
- an **inner product** of $(p_{11},p_{12},p_{21},p_{22})$ and $(q_{11},q_{12},q_{21},q_{22})$: one number.
Separately that is $9+4=13$ multiplications. Schönhage does it in ten. Extend the $p$'s to a
$3\times3$ matrix $\hat p$ whose columns sum to zero, and the $q$'s to $\hat q$ whose rows sum to zero:
$$
\hat p=\begin{pmatrix}p_{11}&p_{12}&0\\ p_{21}&p_{22}&0\\ -p_{11}-p_{21}&-p_{12}-p_{22}&0\end{pmatrix},\qquad
\hat q=\begin{pmatrix}q_{11}&q_{12}&-q_{11}-q_{12}\\ q_{21}&q_{22}&-q_{21}-q_{22}\\ 0&0&0\end{pmatrix}.
$$
The ten products are $P_{ij} = (x_i+\hat p_{ij})(y_j+\hat q_{ij})$ for $i,j\in\{1,2,3\}$, plus
$P_0 = -(x_1+x_2+x_3)(y_1+y_2+y_3)$. Output $z_{ij}$ reads $P_{ij}$ alone. Output $z_0$ is the sum of all
ten. Expand $z_0$: the $x_iy_j$ terms cancel against $P_0$; the cross terms $x_i\hat q_{ij}$ and
$\hat p_{ij}y_j$ sum to zero because of how $\hat p$ and $\hat q$ were padded; what remains is
$\sum \hat p_{ij}\hat q_{ij} = \sum p_{ij}q_{ij}$, the inner product, exactly. The nine $z_{ij}$ are
$x_iy_j$ plus an error
$$
E = \sum_{i,j}\left(x_i\hat q_{ij}+\hat p_{ij}y_j+\hat p_{ij}\hat q_{ij}\right) z_{ij},
$$
and every term of $E$ pairs an outer output with at least one *inner* input. Schönhage stated this as a
border-rank identity with an $\varepsilon$ that goes to zero; the paper sets $\varepsilon=1$ and argues
the error away combinatorially instead.
I did not want to take Lemma 6 on trust, so I wrote the ten linear forms down as coefficient tables and
expanded the identity symbolically, monomial by monomial. The left-hand side and $G+E$ agree on all 33
nonzero monomials, every coefficient is $\pm1$, and the widget above evaluates the same forms on random
integers. Two structural facts matter later, and both are visible in the widget: only $P_{ij}$ feeds
$z_{ij}$, and every term feeds $z_0$.
### Recursing on strings
Apply the identity at $L$ levels and you get a tree with $10^L$ leaves, one per string of $L$ terms.
Each level independently picks "outer" or "inner", so one run computes $2^L$ different matrix products
at once. Restrict to the products that pick "inner" at exactly $m$ levels. Each of those multiplies a
$3^{L-m}\times 4^m$ matrix by a $4^m\times 3^{L-m}$ one, and there are $K=\binom{L}{m}$ of them, all
completely independent: you can feed any $K$ pairs of matrices into one run (Lemma 9). The error $E$
never reaches those outputs, because an $E$ term needs an inner input at a level where the output is
outer, which would give the input string more than $m$ inner levels, and such inputs are set to zero.
I implemented that recursion directly in Python (a dictionary per array, no tricks) and fed it random
matrices: for $L=3, m=1$; $L=4, m=1$; and $L=4, m=2$, every one of the 243, 2,916 and 486 checked
output entries equals the true $X_QY_Q$. Tiny, but it confirms that the indexing in Section 2.3 means
what I think it means.
To multiply a big $N\times D$ by $D\times N$, the paper cuts $X$ into row blocks of $3^{L-m}$ rows and
$Y$ into column blocks, groups $\lfloor\sqrt K\rfloor$ blocks into a band, and treats a row band
times a column band (a "tile") as one run of the recursion. With $D=4^m$ fixed by the problem, $L$ is
the knob. The paper sets $L = 19m$. Computing the whole product that way would be wasteful (about
$N^2D^{0.2}$ operations; $L=10m$ is the efficient choice for full products). The reason for 19 shows up
in the next step.
## The new idea: visit only the leaves you need
Two changes turn the full multiplication into the sparse one.
The first change shares the encodings. The number multiplied at leaf $\tau$ is $\Phi_\tau(a)\cdot\Psi_\tau(b)$,
where $\Phi_\tau(a)$ depends only on the left input array and $\Psi_\tau(b)$ only on the right. A row
band takes part in many tiles, so its $10^L$ encoded numbers are computed once and reused. The condition
$N\ge D^{18}$ exists mostly to make this one-off cost negligible.
The second prunes the recursion. Each call receives the set of output strings wanted from it and only
recurses into children that feed one of them. The algorithm, `Pruned`, visits exactly the leaves that
contribute to some wanted entry, each once, however many entries share it (Lemma 10). So the running
time is the *size of the union* of the wanted entries' leaf sets, not the sum.
The sum alone would be a disaster. One output entry, with inner set $Q$ of size $m$, is fed by $10^m$
leaves: at its $m$ inner levels a leaf may pick any of the ten terms, while at the other $L-m$ levels it
must pick the one $P_{ij}$ matching the entry's $z_{ij}$. $10^m = D^{\log_4 10}\approx D^{1.66}$, worse
than computing the inner product directly with $D$ multiplications. The whole argument is about how
much those leaf sets overlap.
The paper classifies leaves by **order**: $m$ minus the number of levels at which the leaf picks $P_0$.
The order-0 leaf of an output entry picks $P_0$ at all its inner levels. It is the entry's **private
leaf**, and no other entry uses it. A leaf of order $d$ swaps $P_0$ for one of the nine $P_{ij}$ at $d$
of those levels, and because $P_{ij}$ also serves the outer product, that leaf is shared by every
output entry whose inner set contains the leaf's remaining $m-d$ $P_0$ levels.
Two counts carry the proof:
$$
\alpha_d = \binom{m}{d}9^d \ \ \text{(order-}d\text{ leaves feeding one entry)},\qquad
\beta_d = \binom{L}{m-d}9^{L-m+d} \ \ \text{(order-}d\text{ leaves in the whole tile)}.
$$
$\beta_0 = M$, the number of output entries in a tile (one private leaf each). For $L=19m$,
$$
\frac{\beta_d}{\beta_{d-1}} = \frac{9(m-d+1)}{L-m+d} \le \frac{9m}{18m+1} < \frac12,
$$
so the total number of order-$d$ leaves halves with every step in $d$. There lies the reason for $L=19m$:
at $L=10m$, the ratio is close to 1 for small $d$ and the high-order leaves are as numerous as the
entries themselves.
Now bound the union for a wanted set $U$ two ways at each order and take the smaller: charge each
wanted entry for its own order-$d$ leaves ($|U|\alpha_d$), or just take every order-$d$ leaf that exists
($\beta_d$). For small orders the first is smaller, for large orders the second. Splitting at $d=m/9$,
$$
|\mathrm{Leaves}(U)| \le \sum_{d=0}^{m}\min\{|U|\alpha_d,\ \beta_d\} \le D^{-1/18}\left(\sqrt D\,|U| + 2M\right),
$$
where the small-order side uses the inequality $72\cdot(9/8)^9 < 208 < 256$ (it comes to 207.83; I
checked). With $|U| = M/\sqrt D$, that is $O(M/D^{1/18})$ leaves for the tile's wanted entries:
fewer than one per entry of the tile, and far below the $M\sqrt D$ of the inner-product route. Paying
$O(\log^2 D)$ per leaf for the bookkeeping gives Theorem 5, $O(N^2\log^2 D/D^{1/18})$.
The widget computes those two bounds from the paper's formulas, in log space, for any $m$ and any
ratio $L/m$. At $L=19m$ and $m=9$ ($D = 4^9 = 262{,}144$) the bound lands 2.01 times below $M$, right
on the paper's $D^{1/18} = 2$. Slide the ratio down to $L=10m$ and the bound rises *above* $M$ for every
$m$: the pruning buys nothing. It is the clearest demonstration I know of why the exponent 18 is in the
theorem.
The data-structure version in Section 4 reuses this split. Preprocessing adds up the high-order leaves
into "boxes" ahead of time; a query for one entry, not known in advance, reads its few low-order
leaves plus a few boxes. With $L=21m$ and switching order $m/9$, preprocessing costs
$O(N^2/D^{0.063})$ and each query $O(D^{0.437})$ (Corollary 26), which improves the saving from
$D^{1/18}\approx D^{0.056}$ to $D^{0.063}$ and is where the headline exponents come from. The authors
say they derived this version themselves, along with its consequences for hinted Online
Matrix-Vector multiplication. The theoretical ceiling of the technique is $D\le N^{0.1204}$, set by the
identity $\binom{10m}{m}9^{9m}\approx 10^{10m}$: at $L=10m$ a tile has as many outputs as the recursion
has leaves.
Why Schönhage and not the identities behind today's best $\omega$? Footnote 4 is candid: "prior to
this work, the authors had tried approaches like this using the Coppersmith–Winograd identities [CW90]
and more, without success." The argument depends on two properties of Schönhage's tiny identity:
each $z_{ij}$ is fed by a single term, and every coefficient is $\pm1$. Those are precisely the details
that tensor-rank language abstracts away, which may be part of why nobody looked.
## How small is 0.0008?
Smaller than any input you will ever have. I worked the numbers out because "galactic" gets used loosely.
The speedup the exponent buys for 3SUM is $n^{0.000875}$. For a billion numbers that is 1.018, a 1.8%
improvement, *with every constant set to 1*. To be twice as fast as $n^2$ on exponent alone, you need
$n = 2^{1143}$, about $10^{344}$. For APSP the saving is $n^{0.000583}$ and the 2x point is
$n = 2^{1714}$, about $10^{516}$. There are roughly $10^{80}$ atoms in the observable universe.
The constants are not 1, and they are where the real cost hides:
- Theorem 5 needs $N\ge D^{18}$. Even the smallest legal case, $D=4$ ($m=1$),
needs $N\ge 4^{18}\approx 6.87\times10^{10}$, and its saving $D^{1/18}$ is 1.08, which the
$O(\log^2 D)$ factor eats immediately.
- The encodings are enormous. At $m=1$, $L=19$ and every band's encoding has $10^{19}$ numbers. A saving of 2x
from $D^{1/18}$ needs $m=9$, $L=171$ and encodings of $10^{171}$ numbers.
- The proof of Corollary 26's $D^{0.063}$ bound checks its inequalities only for
$m\ge60$, that is $D\ge 4^{59}\approx 3.3\times10^{35}$, and treats smaller $D$ as "bounded by a
constant". Through the Exact Triangle reduction that means $n\ge 10^{639}$ before the improved
machinery is doing anything.
The authors do not pretend otherwise: "The new algorithms are algebraic and potentially impractical in
their current form: the constants hidden in the $O(\cdot)$ are enormous, and the exponents can likely be
improved." If you run 3SUM or shortest paths in production, nothing changes for you. If you write a
paper that says "$X$ needs $n^2$ time unless 3SUM is false", a lot changes.
## What falls, what loses its evidence, what stands
The map is worth reading carefully, because the direction of each arrow decides what happened.
Every problem *equivalent* to 3SUM or APSP gets a faster algorithm: the whole APSP class
(Negative Triangle, Minimum Weight Cycle, Replacement Paths, Second Shortest Simple Path, Radius,
Median, Betweenness Centrality for unique shortest paths, Metricity, Tree Edit Distance with integer
costs, Maximum Subarray, the Wiener Index) and the whole 3SUM class (GeomBase, All-Numbers 3SUM,
Convolution-3SUM, 3-Linear Degeneracy Testing such as finding a 3-term arithmetic progression, and
counting 3SUM solutions). Exact Triangle drops to $O(n^{2.9983})$. Zero-, Min- and Max-Weight $k$-Clique fall below $n^k$
through the classical folding into triangles. The $(\min,+)$-convolution class falls (Superadditivity
Testing, Tree Sparsity, Maximum Consecutive Subsums), and with it Knapsack in $\tilde O(n+t^{2-\delta})$,
randomized for 0/1. Directed unweighted APSP beats Zwick's $n^{2.5275}$ for the first time in over two
decades without help from faster matrix multiplication.
I wondered whether the integer hashing made this an artefact of bounded words. It does not: real
numbers fall too. With randomness, Chan, Vassilevska Williams and Xu's reduction from real-valued 3SUM
and APSP to sparse triangle *counting* uses only additions, subtractions and comparisons (Fredman's
trick), and the thin-product algorithm counts. The results are Las Vegas algorithms in $O(n^{1.998})$
expected time for real 3SUM and $O(n^{2.998})$ for real APSP and the real $(\min,+)$ product.
Problems that were only 3SUM-hard or APSP-hard get nothing. Three collinear points among $n$ points
in the plane, the original 3SUM-hard problem, has no new algorithm, because the reduction runs from 3SUM
*to* it. Its $n^2$ bound is now simply unexplained. The same goes for the dynamic graph lower bounds
(reachability, shortest paths, subgraph connectivity, matching) and the set-disjointness data-structure
bounds for larger universes. Those were the papers whose conclusions depended on the hypotheses, and
they now need a different assumption.
Lower bounds in restricted models remain true and matter less. Kerr's $n^3$ bound for
$(\min,+)$ straight-line programs and the $\Omega(n^2)$ bound for 3-linear decision trees still hold;
the new algorithms escape those models by hashing the weights away and counting triangles with integer
matrix products.
SETH and Orthogonal Vectors are untouched, and so are OMv without hints, $k$-SUM and $k$-XOR for
$k\ge4$, and 3SUM-Indexing. The paper gives reasons rather than hope: 3SUM, APSP and Exact Triangle
always had fast nondeterministic and co-nondeterministic algorithms and shallow decision trees
(near-linear depth for 3SUM and Exact Triangle, $\tilde O(n^{2.5})$ for APSP), while CNF-SAT and OV
have neither. It also adds a sharp corollary: if a deterministic fine-grained
reduction from CNF-SAT or OV to 3SUM, APSP or Exact Triangle existed, SETH itself would now be false.
### Where attention comes in
This last point is the one most readers of this site will care about. The standard argument that exact
softmax attention cannot be computed in truly subquadratic time rests on SETH, not 3SUM. Keles,
Wijewardena and Hegde ([arXiv 2209.04881](https://arxiv.org/abs/2209.04881)) prove self-attention is
"necessarily quadratic in the input length, unless the Strong Exponential Time Hypothesis (SETH) is
false", and Alman and Song ([arXiv 2302.13214](https://arxiv.org/abs/2302.13214), the same Alman) show
approximate attention with entries of size $\Theta(\sqrt{\log n})$ has no $n^{2-\Omega(1)}$ algorithm
under SETH. Both bounds survive this paper intact. If you were hoping the quadratic cost of
[attention](/articles/attention-mechanisms) had just become negotiable, it has not; the
[linear-attention designs](/articles/linear-attention-state-roundup) still pay for subquadratic time
with a different, approximate operator.
One attention-adjacent result does fall at the edge. Van den Brand, Song and Zhou proved their
data structure for *dynamic* attention maintenance conditionally optimal under a variant of a hinted OMv
conjecture. Section 5.4 shows the new data structure refutes that variant for thin hints, so for
$\tau < 0.1204$ that optimality claim "needs a new hypothesis". The algorithm itself is not faster; what
changed is the evidence that it could not be beaten.
## Who found it
The methodology section is unusually specific, and I think it is the most important paragraph in the
paper for anyone outside theory. An Anthropic employee was using an internal research model on open
problems in cryptography, one of them about constructions based on the average-case hardness of
Zero-$k$-Clique. "Claude was tasked with verifying and improving the constructions, but instead
developed this algorithm, first for the average case, then for the worst case. The session used 16M
output tokens with no human input." Anthropic shared it with the authors in September 2026 under a
confidentiality agreement and offered compensation.
The division of labour is stated precisely too. What Claude produced was "essentially the algorithm in
Section 2, although presented differently and with other numerical parameters", plus a different
reduction from Exact Triangle that the authors replaced with the known ones. The data-structure version,
the hinted-OMv consequences and the presentation are the authors'. After the paper was written, a model
certified the main theorems in Lean 4 with Mathlib (Theorem 19, Theorem 22 and the Zero-Weight case of
Corollary 39, with all lemmas they rely on); the formalization is in Anthropic's `formal-math`
repository under `3sum-apsp`. I did not read or build that formalization, so I cannot tell you how
faithfully the Lean statements match the paper's; the [Thomson N=7
article](/articles/thomson-n7-lean) is a good reminder that a machine-checked proof is only as good as
its statement.
The irony is hard to miss. The model was asked to make a *hardness* assumption more useful, and it
broke the assumption instead. Cryptography built on fine-grained hardness of Zero-$k$-Clique has just
lost its worst-case footing, since the paper also refutes the Zero-Weight $k$-Clique hypothesis.
## What people are saying
Two days in, I found no written response from a fine-grained complexity researcher outside the author
list, and I will not invent one. The paper was discussed on Hacker News within hours. The most useful
comments there come from people who read it. User thomasahle summarised the technique accurately:
"interpret rectangular matrix algorithms like Schonhage's as a tree, and then very carefully extract
only some of the entries." User dgacmu compared it to the early improvements to the matrix
multiplication exponent: "it has a very similar feel to Stothers' and then Virginia Williams' earlier
improvement on matrix multiply", which reopened a stuck problem without producing anything practical.
The sceptical reading came from jltsiren, who called it "an entire house of cards collapsed" for
conditional lower bounds and worried that specific formulations of hardness are now "fixed targets for
the AI to attack". I think that last worry has it backwards. A hypothesis that falls to a 0.0008
improvement was stated too sharply, and the paper's own conclusion already proposes replacements:
restrict the hypotheses to combinatorial algorithms, or move the conjectured hardness to the balanced
sparse triangle problem with its $m^{4/3}$ bound, which this technique does not touch.
## What I take from it
Three things.
The technique is small. Strip away the reductions and the paper's contribution is a counting argument
about which leaves of a recursion tree a sparse set of outputs needs, applied to a 1981 identity and a
1982 algorithm (Coppersmith's rectangular multiplication). The authors compare the pruning to FFT
pruning and trimmed Möbius inversion. The genuinely new piece is the count in Section 2.4.3. Ideas this
small are usually the ones that get improved fast, and the paper says outright that better exponents
already exist and were left out for clarity.
Reductions are algorithms. Every arrow in Figure 1 was drawn to prove a lower bound, and every one of
them just became a delivery route for an upper bound. The losses those reductions take (a half, a
third) suddenly matter, and so does work like Sheffield, Vassilevska Williams and Xi's result that
the one-third loss is optimal for black-box reductions.
And the claim at the top of the abstract deserves to be read literally. A model, unprompted, found a
polynomial improvement over problems that had resisted the field since the 1970s, and two of the
people best placed to judge it (both are co-authors of the current best bounds on $\omega$) checked
it, simplified it and put their names on it. I have reported on several AI-for-math results on this site.
This is the first where the result itself, not the fact that a model found it, is the headline.
## How I checked
I read the arXiv HTML and PDF of 2610.06783v1 in full, with Sections 1 to 3 and 4.4 in detail. The five
figures are cropped from the PDF rendered at 300 dpi. In plain Python I wrote out Schönhage's ten
linear forms from Section 2.2 as coefficient tables and compared the expanded left-hand side with
$G+E$ monomial by monomial (they agree on all 33 monomials); implemented the `Full` recursion of Section
2.3 and checked Lemma 9 against direct matrix products for $(L,m) = (3,1), (4,1), (4,2)$; recomputed
$\alpha_d$ and $\beta_d$ for Figure 6 (1, 18, 81 leaves shared by 1, 5, 15 entries) and the worst ratio
$\beta_d/\beta_{d-1}$ at $L=19m$ (0.474 at $m=1$, below 1/2 for every $m$ I tried); evaluated the Lemma
11 sum in log space for the widget; and redid every exponent: $2-1/1296 = 1.99923$, $3-1/1944 = 2.99949$,
$0.0315/18 = 0.00175$, $2-0.000875 = 1.999125$, $3-0.000583 = 2.999417$, $\Lambda\approx4.199\times
10^{10}$ against $4^{18}\approx6.872\times10^{10}$, $q=0.4277$, $\gamma = 0.0640$ and
$\varepsilon^*=\ln4/(5\ln10) = 0.1204$. All match the paper. The practicality thresholds are my own
arithmetic from the stated exponents with constants set to 1. I did not read the Lean formalization,
did not verify the reductions I describe as cited, and did not check Sections 5.1 to 5.3 beyond reading
them. The expert-reaction section reflects what I could find on 7 October 2026: the Hacker News threads
and secondary write-ups, none from named researchers in the area.