Deterministic (min, +) and APSP exponents fall from 2.9995 to 2.9964

Simple, Faster (min, +) Matrix Multiplication and APSP

Barna Saha, Christopher Ye

cs.DS

2026-10-14

Using thin matrix multiplication as a sparse certificate, bounded-integer (min, +) products and APSP run deterministically in Õ(N^2.9964), under Anthropic's N^2.9995.

What problem this solves

All-pairs shortest paths asks for every distance in an N-vertex graph. Floyd-Warshall takes O(N^3). Later algorithms removed only subpolynomial factors. Williams (2018) reached N^3 / 2^{Θ(√log N)}, still short of truly subcubic time, meaning N^{3-δ} for a fixed δ > 0. Fine-grained complexity treated the nonexistence of such an APSP algorithm as a central hypothesis.

(min, +) matrix multiplication matches APSP up to polylog factors. Each output is mink (A[i, k] + B[k, j]): addition stands where ordinary multiplication would, and a minimum stands where a sum would. Ordinary matrix multiplication already satisfies ω ≤ 9/4. This family stayed glued to cubic.

In 2026 Alman and Vassilevska Williams, called the Anthropic breakthrough in the note, gave the first deterministic truly subcubic bound, O(N^{2.9995}). The hypothesis does not hold. The same paper also has a Las Vegas algorithm for real weights in expected O(N^{2.998}). The deterministic gap under 3 is only 0.0005. This note lowers the integer exponent and returns the proof to a phased framework from 2016.

Method

The target is the (min, +) product of two N×N matrices whose entries are polynomially bounded integers. A shift makes every entry positive.

The product reduces to witness equality: given A, B, and a candidate C, decide whether each (i, j) has a k with A[i, k] + B[k, j] = C[i, j]. Halve every entry, round up, and recurse. If X′ is that product, the true value sits between 2X′ − 2 and 2X′ inclusive, hence in a set of three integers. Three witness checks keep the smallest value that has a witness. Each halving of the magnitude U multiplies the cost by a log U factor.

Cut the inner index into blocks of length B. A block is a witness when it contains a true k. Primes come from [P, 2P] with P ≫ B log U. Differences inside a false block are nonzero and at most 3U in absolute value, so few of their prime factors land in that interval. The prime-number theorem puts Θ(P / log P) primes there, and a random prime marks a false block as a candidate with probability at most 1/2. After ⌈log S⌉ independent primes that probability is at most 1/S. True blocks always remain.

Checking those congruences one entry at a time would be cubic. Thin matrix multiplication, Theorem 25 of the breakthrough, computes up to N^2 / D^κ entries of an ordinary product when the inner dimension satisfies D ≤ N^ε for ε < (ln 4)/(5 ln 10) ≈ 0.1204, in deterministic time O(N^2 log^2 D / D^γ).

The matrices are Boolean. Columns are pairs (k, a) with a a residue mod p. One matrix marks the residue of A; the other marks the residue of B that completes a target residue r. A positive product means the block is a candidate for that prime. The inner dimension is Bp, so the theorem applies once 2BP ≤ N^ε.

Only candidate blocks are then scanned, and each (i, j) stops at the first true k. True blocks cost O(N^2 B). False candidates number O(N^3 / (BS)) in expectation and take expected time O(N^3 / S).

Table 2 of the breakthrough supplies ε = 0.056, κ = 0.5, and γ = 0.0653. Set S = N and take B slightly below N^{ε/2} / log U. Balancing the dominant terms gives Õ(N^{3 − γε} log U). Because γε = 0.0036568, the exponent is 2.9963432. Polynomial bounds fold log U into the Õ, which is why the theorem states Õ(N^{2.9963432}). The abstract rounds the display to 2.9964.

Prime sampling is the only randomness. The deterministic algorithm bisects blocks and searches depth-first, stopping at the first true witness of each output. A potential Φ caps false candidates on each level. Φ is awkward to compute, since that requires telling true witnesses from false ones, so the algorithm minimizes a constant-factor proxy Z(p), evaluated for every candidate prime by a matrix product over a polynomial ring. Queries use the data-structure form, Corollary 31: cheaper preprocessing, costlier lookups. Higher levels issue fewer queries, and the budget moves toward preprocessing. With c = 21, t = 8, and the same ε and γ, the deterministic bound matches.

Results

The note compares running-time bounds and reports no experiments.

AlgorithmSettingTime
Floyd-Warshallgeneral graphsO(N^3)
Williams 2018general graphsN^3 / 2^{Θ(√log N)}
Alman and Vassilevska Williams 2026deterministicO(N^{2.9995})
Same paper, real weightsLas Vegas, expectedO(N^{2.998})
This note, Theorem 1.1polynomially bounded integers, Las Vegasexpected Õ(N^{2.9963432})
This note, Theorem 1.3same input, deterministicÕ(N^{2.9963432})

On the printed exponents, the deterministic bound moves from 2.9995 to 2.9963432. The gap below 3 grows from 0.0005 to 0.0036568, about 7.3 times larger. Polylog factors inside Õ do not close it. Known reductions carry the same bound to APSP, negative triangle, replacement paths, the second shortest simple path, metricity, (min, +) verification, weighted tree edit distance, and the 2D maximum subarray, up to polylog factors.

Real weights are unchanged. Expected O(N^{2.998}) is still the breakthrough bound for real-weighted APSP. This note has no direct comparison in that setting.

Why it matters

The step is small. Beating Floyd-Warshall at N^{2.9963432} would take an unrealistic N. The Õ hides the large constants of algebraic matrix multiplication, and the note ships no implementation.

The argument finishes the 2016 phased framework of Bringmann, Grandoni, Saha, and Vassilevska Williams. That framework already produced an additive approximation in truly subcubic time and showed that the surviving triples are subcubic in number. It lacked a sparse certificate with no structural assumption on the matrices. The thin product provides one. A better ε or γ in Theorem 25 lowers 3 − γε at once. Saha coauthored the 2016 framework.

The randomized algorithm first leaves three integers at each position, then uses modular primes to drop most false blocks. The thin product certifies the rest, and a final scan checks whatever survives. The deterministic algorithm keeps the same exponent and adds a hierarchy, a potential, and matrix products over a polynomial ring.

Limitations

Both theorems need polynomially bounded integers. Real matrices are outside the claim, and the breakthrough's expected O(N^{2.998}) for real-weighted APSP is untouched. Moving the exponent to the reals is left open.

The figure 2.9963432 is 3 − γε, and γε comes from the earlier thin-product theorem. The chosen ε = 0.056 sits well below the allowed ceiling near 0.1204 so that γ = 0.0653 and κ = 0.5 can be used together. If that black box stays put, this exponent stays put.

The deterministic constants are tight. One derivative combination has to stay under 0.5, and R21(0.075) = 0.05663927 has to stay above ε. The note says public ChatGPT Pro checked the randomized algorithm, tuned the parameters, and ran the numerics. The later ideas for the deterministic algorithm came from ChatGPT Pro too; the authors checked the arguments and rewrote the proof. Prompting ChatGPT with the algorithm also produced a lower running time and a route to real matrices through known reductions. The authors have not confirmed that those suggestions fit this framework.

Simple refers to how the modules split. The deterministic half of the note is not simple. The preliminaries cite ω ≤ 9/4, and the proof says a weaker matrix-multiplication exponent is enough.

Terms

Source

What people are saying

Related papers

All paper explainers