pipette
ESEspañol

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

Barna Saha, Christopher Ye

Preprint

In the authors' words

In this note, we provide a deterministic algorithm that computes the -Matrix Product of two matrices and with polynomially bounded integer entries in time, improving upon the exponent of 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 of in truly subcubic time such that the number of remaining triples is truly subcubic. This provided strong evidence that a truly subcubic -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.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 17 pages