CS Paper Radar

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

Barna Saha, Christopher Ye

cs.DS ·submitted 2026-10-14 14:48 UTC · v1
theory

Abstract

In this note, we provide a deterministic algorithm that computes the $(\min, +)$-Matrix Product $C = A * B$ of two $N \times N$ matrices $A$ and $B$ with polynomially bounded integer entries in $\tilde{O}(N^{2.9964})$ time, improving upon the exponent of $O(N^{2.9995})$ time obtained in the recent breakthrough by Anthropic (Alman and Vassilevska Williams, 2026). Our algorithm uses a phased approach first proposed by Bringmann, Grandoni, Saha, and Vassilevska Williams in 2016. The phased approach produces an approximation $\tilde{C}$ of $C$ in truly subcubic time such that the number of remaining triples $(i,k,j): A_{i,k}+B_{k,j} < \tilde{C}(i,j)$ is truly subcubic. This provided strong evidence that a truly subcubic $(\min, +)$-Matrix Product and therefore, a truly subcubic algorithm for All Pairs Shortest Paths (APSP) may exist. However, to find the remaining triples in subcubic time, a sparse certificate is needed whose construction was not known. We use the thin matrix product theorem of the recent breakthrough to provide such a certificate. This gives a simple modular subcubic algorithm for APSP.

Comment
17 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Lower Bound of 22 for 3x3 Matrix Multiplication over the Integers

cs.CC ·2026-10-01 ·Isaac Rudich, Louis-Martin Rousseau
publishedtheory similarity 0.77
Abstract

Strassen showed that two 2x2 matrices can be multiplied with 7 multiplications instead of 8. Applied recursively, his algorithm multiplies two nxn matrices with O(n^2.807) multiplications, beating the naive O(n^3). The best known 3x3 recursive matrix multiplication algorithm uses 23 multiplications O(n^2.854). The best published lower bound of 21 (on algorithms with integer constants) leaves room for an algorithm with O(n^2.771) multiplications, and thus does not rule out the possibility of an algorithm that would beat Strassen's. We prove a lower bound of 22 multiplications for any 3x3 recursive algorithm with integer constants, proving that no such algorithm can do better than O(n^2.814) multiplications, and eliminating the possibility of a 3x3 algorithm that beats Strassen's 2x2 method. The proof builds on a recent decomposition method from Wang, who approached the problem by turning it into 496 subproblems. We provide exact solutions for 359 of them. The proof is in Lean; verification requires auditing only a few short files. The Lean formalization directly encodes statements about the limitations of recursive algorithms for matrix multiplication, as opposed to just a statement about the rank of the problem.

0.19

Combinatorial Boolean Matrix Multiplication in $n^3 / 2^{Ω(\sqrt{\log n})}$ Time

cs.DS ·2026-11-04 ·Piaoyang Cui, Yiming Liu, David P. Woodruff
similarity 0.74
Abstract

For over fifty years, combinatorial algorithms for Boolean matrix multiplication (BMM) and triangle detection saved only polylogarithmic factors over cubic time. At STOC 2024, Abboud, Fischer, Kelley, Lovett, and Meka broke this barrier with a deterministic $O(n^3 / 2^{Ω((\log n)^{1/7})})$-time algorithm, and asked whether $n^3 / 2^{Ω(\sqrt{\log n})}$ time is achievable. We answer this question in the affirmative, giving deterministic combinatorial algorithms for both BMM and triangle detection running in $O(n^3 / 2^{Ω(\sqrt{\log n})})$ time. Following Abboud et al., we decompose $(A,B)$ into pairs of submatrices $(A_k,B_k)$, called \emph{pieces}, each of which is either sparse or pseudorandom in a sense that forces $A_k\star B_k$ to be nearly all-ones on its vertex sets. Whereas their decomposition produces $2^{O(d^7)}$ pieces at regularity parameter $d$, we obtain $2^{O(d^2)}$ pieces, directly improving the runtime exponent from $(\log n)^{1/7}$ to $\sqrt{\log n}$. Prior work found pseudorandom pieces by repeatedly restricting to denser submatrices, paying worst-case vertex losses at each step that compounded across nested recursion levels, together with an expensive derandomization step. We eliminate the extra powers of $d$ by matching the vertex loss at each step to the size of its density jump so losses telescope across scales, derandomizing witness search via $L_d$-norm estimation so the sampler length stays $2^{O(d)}$, and bounding overlap across the recursion with a fractional density-weighted volume budget rather than raw submatrix volume.

0.20

A simplified proof of polynomial improvements for 3SUM and APSP

cs.CC ·2026-10-11 ·Sankeerth Rao Karingula, Shachar Lovett
publishedhot directionhighly cited similarity 0.73
Abstract

We give a simplified proof of the polynomial improvements for integer 3SUM and all-pairs shortest paths (APSP) established by Alman and Vassilevska Williams, with weaker exponents. The central ingredient is selected-entry matrix multiplication: computing a prescribed set of entries of a product of dense rectangular matrices. Starting from Schönhage's inner/outer-product identity, we construct a multiplication rule that shares intermediate products among many outputs. We apply this rule recursively and bound the work by counting the requested entries at each level. Applied to incidence matrices, the algorithm solves Offline Set Disjointness over a small universe. Known deterministic reductions then yield truly subquadratic integer 3SUM and truly subcubic APSP for polynomially bounded integer inputs.

0.58

Truly Sub-$3^n$ Min-Sum Subset Convolution and Join Ordering

cs.DS cs.DB ·2026-10-07 ·Mihail Stoian
hot direction similarity 0.72
Abstract · Feedback welcome; v2: fixed technique naming

We present a deterministic reduction from min-sum subset convolution to min-plus matrix product. We show that if the min-plus product of two $D\times D$ matrices with $β$-bit integer entries can be computed in $D^{3-δ}\operatorname{poly}(β,\log D)$ time for a fixed rational $0<δ<1$, then min-sum subset convolution on an $n$-element universe can be solved in $(2+2^{-δ})^n 2^{O(\sqrt n\log(n+1))}\operatorname{poly}(n,β)$ time. Instantiating this reduction with the recent breakthrough on subcubic min-plus matrix product by Alman and Vassilevska Williams gives a Las Vegas algorithm with expected running time $O^*(2.9987^n)$ and a deterministic algorithm with running time $O^*(2.9997^n)$, strictly breaking the longstanding $3^n$ computational barrier. Notably, these speedups translate directly to database query optimization, yielding the same expected and deterministic running-time bounds for join ordering under the $C_{\mathrm{out}}$ cost function.

0.27

3SUM Made Simpler (Without Matrix Multiplication), $k$-SUM Hypothesis Refuted for Odd $k$, and Real 3SUM/APSP Derandomized

cs.DS ·2026-10-30 ·Timothy M. Chan, Reina Itakura, Zhiyuan Ma, Yuancheng Yu
highly cited similarity 0.70
Abstract

Recently, a truly subquadratic algorithm for the 3SUM problem and a truly subcubic algorithm for the all-pairs shortest paths (APSP) problem were found by Anthropic, as reported by Alman and Vassilevska Williams (2026). These algorithms relied on a new subroutine for rectangular matrix multiplication with selected output entries, which was obtained by modifying known matrix multiplication techniques of Schönhage (1981) and Coppersmith (1982). 1. We present a different truly subquadratic randomized algorithm for 3SUM for integer inputs. It completely avoids the use of matrix multiplication but instead modifies known dynamic programming algorithms for subset convolution and the zeta transform, which rely only on simple subtraction tricks via inclusion--exclusion (and does not even require fast Fourier transform), and so is conceptually easier to understand (the whole solution is about 5 pages long). 2. Following a similar approach, we obtain a randomized algorithm for $k$-SUM for integer inputs for odd constant $k$ in $O(n^{\lceil k/2\rceil-\varepsilon_k})$ time for some constant $\varepsilon_k>0$, disproving the $k$-SUM Hypothesis for all odd $k$. 3. Existing reductions from 3SUM and APSP to selected-entries rectangular matrix multiplication were randomized in the case of real-valued input. We present new deterministic reductions, yielding a truly subquadratic deterministic algorithm for Real 3SUM and a truly subcubic deterministic algorithm for Real APSP.

0.35

Optimal Deterministic Fully Sparse Matrix Multiplication

cs.DS ·2026-08-19 ·Omar Graia
similarity 0.70
Abstract

We give the first deterministic algorithm for fully sparse matrix multiplication that attains the optimal running-time exponent. This result matches the best previously known randomized algorithm running-time exponent. Given compatible matrices $A$ and $B$ over an arbitrary associative ring with identity, with $\operatorname{nnz}(A),\operatorname{nnz}(B)=O(n^{δ_{\mathrm{in}}})$ and $\operatorname{nnz}(AB)=O(n^{δ_{\mathrm{out}}})$, our algorithm finds the support of $AB$ and computes the product exactly in $$O\!\left(n^{β_R(δ_{\mathrm{in}},\min\{δ_{\mathrm{out}},2δ_{\mathrm{in}}\})+\varepsilon}\right)$$ operations, where $β_R(δ_{\mathrm{in}},δ)$ denotes the maximum of $δ_{\mathrm{in}}$ and $ω_{δ_{\mathrm{in}},R}(a,1,b)$ over all $a,b\in[0,1]$ satisfying $a+b=δ$. For dense inputs over a commutative ring, this bound simplifies to $O(n^{ω_R((δ_{\mathrm{out}}-1)_+,1,1)+\varepsilon})$. With the current rectangular matrix multiplication bounds, this is nearly quadratic, namely $O(n^{2+\varepsilon})$, for every $δ_\mathrm{out}\le1.321334$, improving the previous deterministic range of $δ_{\mathrm{out}}\le 0.642668$. To prove this result, we develop a general deterministic recovery technique that finds and fixes sparse parts of an unknown matrix while keeping temporary errors in denser parts under control.

0.30

Asteroidal Triples and Friends in (Likely Necessary) Matrix Multiplication Time

cs.DS ·2026-10-15 ·Jakob Nogler, Agnès Totschnig, Virginia Vassilevska Williams
top venue similarity 0.67
Abstract · 32 pages, 6 figures; to appear at SODA 2027

In a seminal paper, Kratsch and Spinrad [SODA 2003 and SIAM Journal on Computing 2006] studied several important problems in structural graph theory that anticipated two trends in fine-grained complexity, both from the upper- and lower-bound side: * From the upper-bound side, for each of these problems the authors give an intermediate running time strictly between $n^ω$ and $n^3$, where $ω<2.371177$ is the matrix multiplication exponent. When optimized, this running time can be made $\tilde{\mathcal{O}}(n^{(3+ω)/2})$. By now, many more problems can be solved in this running time: directed unweighted or node-weighted APSP, a variety of matrix products such as max-min and dominance, RNA Folding and many more. For some of these, the community has also developed tools suggesting that this intermediate running time is necessary. * From the lower-bound side, the authors give lower bounds of $n^{ω-o(1)}$, conditioned on three natural hardness hypotheses on the complexity of quantified variants of triangle detection that account for different types of hardness of such problems. Despite this, it has remained open for over 20 years which of these two pieces of evidence reflects the truth for the problems that Kratsch and Spinrad study: whether the intermediate running time is indeed necessary and stronger lower bounds hold, or whether the hardness evidence of Kratsch and Spinrad is essentially tight. In this paper, we resolve this question and show that the latter is the case: all problems admit an $\tilde{\mathcal{O}}(n^ω)$ time algorithm. As an additional contribution, we make partial algorithmic progress on further problems in structural graph theory of intermediate complexity, improving over previous work [Chiu and Lu, STACS 2022 and Information and Computation 2024][Spinrad, Discrete Applied Math 2004].

0.45

Thin matrix products up to D <= N^0.172 and lossless reductions for 3SUM, Exact Triangle and APSP, with 3SUM over abelian groups and a dichotomy for coordinatewise problems

cs.DS ·2026-10-12 ·Ruhollah Majdoddin
theorycode/datahighly cited similarity 0.67
Abstract · 130 pages. Lean formalisation and scripts: https://github.com/Majdoddin/formal-math

Alman and Vassilevska Williams (arXiv:2610.06783) gave the first polynomial improvements over the textbook algorithms for 3SUM and APSP: deterministic algorithms with exponents 1.9992 for 3SUM, 2.9983 for Exact Triangle and 2.99942 for APSP. Their algorithm has two steps: a matrix theorem, computing N^2/sqrt(D) prescribed entries of the product of an N x D and a D x N integer matrix in time N^2/D^gamma, gamma > 0, when D <= N^eps, for every eps < 0.1204; and reductions from the three problems to the lopsided sparse triangle problem. We improve both. With Schönhage's five-term partial-product tensor, the matrix theorem holds for every eps < 0.172. The preprint's reductions keep a quarter of the matrix theorem's saving for 3SUM and a half for Exact Triangle and APSP; ours keep all of it, by calling the counting version of the triangle problem adaptively and building composite moduli one prime at a time. Together this gives deterministic 3SUM in n^{1.9945+o(1)}, and Exact Triangle, (min,+)-product and APSP in n^{2.9945+o(1)}. We also improve on the preprint's proof sketch for 3XOR and solve it deterministically in O(n^{1.99451}). Which other problems on three lists does the method make truly subquadratic? It solves 3SUM over F_p^d for every fixed prime p with 3XOR's exponents, and over every finite abelian group of exponent p^2, such as Z_4^d, in O(n^{1.99726}). For coordinatewise problems with a fixed relation P on every coordinate triple, a certified exhaustive computation shows that every Boolean P, and every functional P over three letters, either is the solution set of an equation over Z, F_2 or F_3, and the problem is then truly subquadratic, or has a gadget for Orthogonal Vectors, and the problem is then hard under the Orthogonal Vectors hypothesis. Over four letters, just four functional relations, up to symmetry, satisfy neither condition.

0.60