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

Abstract

In this note, we provide a deterministic algorithm that computes the $(\min ,+)$-Matrix Product $C=A\ast 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.

arXiv comment17 pages