# Faster all-pairs shortest paths via circuit complexity

arXiv: https://arxiv.org/abs/1312.6680 · HTML: https://mlsanity.com/paper/1312.6680/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Dec 2013.

## Built on by (most cited first, 2 of 2)

- [SPADE: A Spectral Method for Black-Box Adversarial Robustness Evaluation](https://mlsanity.com/paper/2102.03716/) (2021)
- [Subquadratic Algorithms and Hardness for Attention with Any Temperature](https://mlsanity.com/paper/2505.14840/) (2025)

## Abstract (arXiv)

We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two n × n matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-node directed graphs with arbitrary edge weights. On the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost), the algorithm runs in time [fracn32^Omega(log n)1/2] and is correct with high probability. On the word RAM, the algorithm runs in n3/2^Omega(log n)1/2 + n2+o(1)log M time for edge weights in ([0,M] cap mathbb Z)cup∞. Prior algorithms used either n3/(logc n) time for various c ≤ 2, or O(Mαnβ) time for various α > 0 and β > 2. The new algorithm applies a tool from circuit complexity, namely the Razborov-Smolensky polynomials for approximately representing sf AC0[p] circuits, to efficiently reduce a matrix product over the (min,+) algebra to a relatively small number of rectangular matrix products over mathbb F2, each of which are computable using a particularly efficient method due to Coppersmith. We also give a deterministic version of the algorithm running in n3/2^logδ n time for some δ > 0, which utilizes the Yao-Beigel-Tarui translation of sf AC0[m] circuits into "nice" depth-two circuits.