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

Preprint · Barna Saha, Christopher Ye

- Archive id: arxiv:2610.20297
- Published: 2026-10-14
- arXiv: https://arxiv.org/abs/2610.20297
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.20297
- PDF: https://arxiv.org/pdf/2610.20297
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.