PaperlayerView exact revision on arXiv

Source-linked AI summary

Faster all-pairs shortest paths via circuit complexity

Ryan Williams

arXiv:1312.6680v2cs.DScs.CCmath.CO

TL;DR

The paper addresses whether APSP can be solved faster than the longstanding cubic-time bound. It reduces min-plus matrix multiplication to matrix products over F2, obtaining faster randomized and deterministic algorithms while noting practical impediments in the polynomial translation and matrix multiplication components.

  • Problem

    The paper asks whether the O(n^3) APSP bound can be improved, given that the input may contain Θ(n^2 · logM) bits and prior approaches were believed limited to polylogarithmic savings.

  • Method

    The method reduces min-plus matrix multiplication to rectangular matrix multiplication over F2, using circuit-complexity polynomial representations and efficient rectangular multiplication.

  • Results

    The randomized algorithm runs in n^3/2^{Ω(logn)^{1/2}} time on the real RAM and in n^3/2^{Ω(logn)^{1/2}} + n^{2+o(1)} logM time on the word RAM, with high-probability correctness.

  • Takeaways & Limitations

    The paper demonstrates an APSP algorithm faster than n^3/log^k n for every k and extends the approach to other matrix products whose inner products are definable in AC0 or ACC.

  • Takeaways & Limitations

    Practical use may be impeded by quasi-polynomial blowup in the AC0[2]-to-polynomial translation and by Coppersmith’s matrix multiplication algorithm.

Abstract

from arXiv · show

We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two $n \times 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 \[\frac{n^3}{2^{Ω(\log n)^{1/2}}}\] and is correct with high probability. On the word RAM, the algorithm runs in $n^3/2^{Ω(\log n)^{1/2}} + n^{2+o(1)}\log M$ time for edge weights in $([0,M] \cap {\mathbb Z})\cup\{\infty\}$. Prior algorithms used either $n^3/(\log^c n)$ time for various $c \leq 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 AC}^0[p]$ circuits, to efficiently reduce a matrix product over the $(\min,+)$ algebra to a relatively small number of rectangular matrix products over ${\mathbb F}_2$, each of which are computable using a particularly efficient method due to Coppersmith. We also give a deterministic version of the algorithm running in $n^3/2^{\log^δ n}$ time for some $δ> 0$, which utilizes the Yao-Beigel-Tarui translation of ${\sf AC}^0[m]$ circuits into "nice" depth-two circuits.

1 Introduction

The paper challenges the prevailing expectation that general APSP can only gain small poly(log n) improvements, introducing a circuit-based min-plus multiplication algorithm with faster-than-polylogarithmic savings. It also extends the result to related problems and identifies truly subcubic APSP as an open direction.

  • Motivation and contribution: The new APSP algorithm runs faster than n^3/log^k n for every constant k, countering pessimism about surpassing polylogarithmic improvements.The result is based on a faster algorithm for min-plus matrix multiplication, which is equivalent to APSP.
  • Method: The method reduces min-plus products to a small number of rectangular matrix products over F_2 using Razborov-Smolensky polynomial approximations and Coppersmith's fast rectangular multiplication.Min-plus inner products are handled through their low-depth AC^0 circuit structure, avoiding the exponential number-size blowup of the conventional x^a mapping.
  • Applications: The framework yields n^3/2^{Ω(ℓ(n))} real-RAM algorithms for metricity, minimum weight triangle, minimum cycle, second shortest paths, and replacement paths.It also gives a minimum-weight triangle algorithm for any m-edge weighted graph in m^{3/2}/2^{Ω(ℓ(m))} time.
  • Open direction: A deterministic version and a possible extension to truly subcubic APSP remain tied to further circuit translations and more efficient representations of min-plus inner products.The paper points to depth-two threshold-circuit methods as a possible route to an n^{3-ε} algorithm.

2 A relatively short argument for faster APSP

The section develops a faster APSP approach by expressing min-plus inner products as small Boolean circuits and evaluating their polynomial representations across many input pairs. The resulting warm-up algorithm is effective for edge weights bounded by poly(n), with later refinements addressing its remaining weight-dependent factor.

  • The resulting bound is effective for edge weights in {0,1,...,poly(n)}, while the (logM)1+o(1) factor is eliminated in the next section.
  • Min-plus matrix multiplication is a collection of all-pairs min-plus inner products over vector sets.
  • Min-plus inner products on O(d logM)-bit encodings are computable by constant-depth AND/OR/NOT circuits of size (d logM)O(1).
  • AC0 circuits are translated into SYM+ circuits whose AND gates form a polynomial with 2O(log f(e,m) s) monomials and an efficiently computable symmetric output function.
  • A polynomial with at most n0.1 monomials can be evaluated on all n^2 pairs of inputs in n^2 · poly(logn) arithmetic operations using rectangular matrix multiplication.Coppersmith’s method multiplies an n × n^0.172 matrix by an n^0.172 × n matrix in O(n^2 log^2 n) arithmetic operations.
  • The warm-up algorithm applies this reduction to n × d and d × n min-plus products, choosing d small enough that the polynomial has at most n0.1 monomials.The construction first encodes each row and column as a min-plus inner product, then evaluates all resulting pairs through matrix multiplication.

3 Proof of The Main Theorem

The proof combines Fredman’s preprocessing with randomized circuit approximations over F2 to compute rectangular and then square min-plus products faster than cubic time. A union-bound analysis yields high-probability correctness and the stated real-RAM and word-RAM bounds, alongside a deterministic variant.

  • Preprocessing: Fredman’s trick replaces arbitrary entries by ranks while preserving all relevant comparisons and ensuring a unique minimizing index for every matrix entry.The transformed entries lie in {1,...,2n}; the preprocessing costs O~(n·d^2·logM) on the word RAM and O(n·d^2·logn) on the real RAM.
  • Circuit formulation: The proof encodes each minimum as a Boolean expression whose unique true term identifies the smallest minimizing index bit by bit.Because exactly one conjunction is true, the relevant OR can be replaced by XOR, which becomes addition over F2.
  • Circuit approximation: Razborov–Smolensky replacements reduce high-fan-in ANDs to randomized low-depth expressions, producing short F2 polynomials that approximate the comparison circuits.The construction uses e = 2 + log d for the first approximation, while the comparison-circuit approximation achieves per-comparison success at least 1−(t+1)/2^e′.
  • Running time: For d = 2^{δ(log n)^{1/2}}, rectangular products run in n^2·poly(log n)+n·d^2·log M time with high probability, yielding square products in n^3/2^{Ω(log n)^{1/2}} time.The square-product algorithm succeeds with probability at least 1−(log n)/n on the real RAM and has an additional n^{2+o(1)}·log M term on the word RAM.
  • Derandomization: A deterministic APSP algorithm runs in n^3/2^{(log n)^δ} time for some δ > 0, remaining asymptotically faster than n^3/(log n)^k for every k.The deterministic result is stated as Theorem 3.1 on the real RAM.

4 Some Applications

The paper applies its min-plus multiplication results to minimum-weight triangles and to circuit-based reductions for APSP. It also derives a bounded-weight APSP consequence from a hypothesis about efficient SYM◦THR circuits for min-plus inner products.

  • Minimum-weight triangles: A minimum-weight triangle in an m-edge weighted graph can be found in m^{3/2}/2^{Ω(ℓ(m))} time.The proof splits into low-degree and high-degree cases, using direct search for the former and min-plus multiplication on high-degree vertices for the latter.
  • Minimum-weight triangles: The high-degree triangle case reduces to min-plus matrix multiplication on at most 2m/Δ vertices, while the low-degree case takes O(m·Δ) time.A min-plus product computes two-edge shortest-path weights, which are combined with edge weights to test triangles.
  • Circuit implication: Polynomial-size SYM◦THR circuits for bounded min-plus inner products would imply a truly subcubic APSP algorithm on the word RAM.The hypothesis requires threshold weights bounded by 2^{poly(log M)}·2^{n^2} and polynomial-time constructibility.
  • Circuit implication: Given the circuit hypothesis, choosing d = min{1,n^{1/(12k)}/(log M)^k} and reducing square multiplication to n/d rectangular products yields O(n^{3−1/(12k)}·(log M)^k) time.The evaluation procedure handles all n^2 pairs using the stated SYM◦THR circuit algorithm.
  • Bounded weights: For integer edge weights in [0,M], shortest paths have weight at most nM or are ∞, enabling the desired APSP bound through min-plus products with entries up to nM.The resulting running time is n^{3−ε′}·poly(log M) for some ε′ > 0.

5 Discussion

The discussion presents the method as a generic circuit-based framework, identifies possible applications beyond APSP, and highlights practical and theoretical open questions. It also notes substantial engineering challenges for practical implementation.

  • Generality: The approach applies to other matrix products whose inner-product operations are definable in AC0 or ACC and admit suitable dimension reductions.AC0 membership alone is insufficient; the reduction must also decompose length-n inner products into roughly n/d shorter products.
  • Open applications: Subquadratic 3SUM and faster string-matching problems are identified as potential directions for extending the paper’s circuit-based speedups.The discussion specifically asks whether edit distance can be computed in n^2/2^{(log n)^δ} time.
  • Practicality: A practical implementation faces quasi-polynomial polynomial-expansion overhead in the circuit translation and the engineering complexity of Coppersmith’s matrix multiplication algorithm.The paper characterizes turning the theoretical algorithms into high-performance software as a substantial engineering challenge.
  • Sparse graphs: An APSP algorithm for sparse m-edge graphs with roughly O~(mn/2^{(log n)^δ}+n^2) time remains open, even for undirected unweighted graphs.The discussion contrasts this target with known algorithms taking roughly mn/log n time.
  • Truly subcubic APSP: The discussion asks which circuit classes can both compute min-plus inner products and support fast evaluation on many inputs, a route toward truly subcubic APSP.It contrasts min-plus inner products, which are efficiently computable in AC0, with ordinary algebraic inner products, whose multiplication is not in AC0.

A Proof of Lemma 2.1

The lemma shows that min-plus inner products over bounded integer encodings can be computed by constant-depth Boolean circuits. It constructs constant-depth addition, comparison, and minimum circuits, including tie-breaking for multiple minima.

  • Circuit membership: Min-plus inner products on O(d log M)-bit encodings are computable by constant-depth AND/OR/NOT circuits of polynomial size.Thus the min-plus inner product function lies in AC0 for every d and M.
  • Encoding: The encoding reserves t = 3 + log M bits for values in {0,...,M} and represents ∞ as the all-ones t-bit string.The encoding ensures ∞ exceeds 2M and remains absorbing under addition.
  • Addition: A carry-lookahead adder computes t-bit addition in constant depth, with a side circuit forcing every output bit to 1 when either input encodes ∞.Generate and propagate bits allow all carry positions and sum bits to be determined in parallel.
  • Comparison: Comparisons of t-bit nonnegative integers are computable in AC0 by combining equality checks with first-differing-bit tests.The construction rewrites modulo-2 expressions using AND, OR, and NOT gates.
  • Minimum: The minimum of d encoded numbers is computed in AC0 by testing whether each candidate is no larger than every other candidate and selecting its output bits.When minima are not unique, MINBIT selects the minimum index before outputting the corresponding value bit.

B Appendix: Derandomizing the APSP algorithm

The appendix gives a deterministic APSP algorithm by combining Fredman’s trick with a deterministic circuit-to-polynomial reduction, achieving a subcubic running time.

  • A deterministic APSP algorithm runs in n^3/2^(log n)^δ time for some δ > 0.
  • The proof combines Fredman’s trick with the deterministic reduction from circuits to polynomials.
  • The construction starts from an AC^0[2] circuit computing min-plus inner products on length-d vectors.
  • Each circuit is reduced to a symmetric circuit and then to an integer inner product of two 0-1 vectors.
  • When 2^(3 log d + 2 log log n)^c ≤ n^0.1, the reduction yields rectangular 0-1 matrix products and an n^3/d-time min-plus algorithm.

C Appendix: An exposition of Coppersmith’s algorithm

This appendix explains how Coppersmith’s construction supplies the efficient rectangular matrix multiplication needed by the APSP algorithm, including an arithmetic-operation bound over suitable fields.

  • Coppersmith’s construction gives rank O(N^2 log^2 N) for N × N^0.1 × N matrix multiplication.
  • The rank bound implies that N × N^α and N^α × N multiplication takes N^2 · poly(log N) arithmetic operations for α ≤ .172.
  • Later improvements mildly increase the allowed α but achieve N^2+o(1), rather than the required N^2 · poly(log N) time.
  • The exposition emphasizes that converting the rank theorem into an explicit efficient algorithm is not immediate, particularly because of possible non-uniformity.

C.1 A short preliminary

The preliminary section introduces the structured decomposition paradigm underlying Coppersmith’s algorithm and explains how bilinear matrix multiplication algorithms support it.

  • Bilinear algorithms can be expressed as trilinear forms whose coefficients encode the matrix-product outputs.
  • The trace representation lets one bilinear algorithm induce related algorithms for computing different matrix factors and their transposes.
  • Coppersmith’s algorithm follows Schӧnhage’s paradigm of replacing arbitrary products with slightly larger products having structured nonzeroes.
  • The decomposition preprocesses input matrices into sparse partial matrices and explicit Vandermonde-style matrices whose product recovers the original multiplication.

C.2 The algorithm

Coppersmith’s algorithm recursively multiplies sparse structured matrices, uses Vandermonde preprocessing and postprocessing, and tensors the resulting procedures into efficient rectangular multiplication.

  • C.2 The algorithm: Vandermonde matrices are chosen for succinct representation, efficient vector multiplication, and invertible square submatrices.
  • C.2 The algorithm: The recursive core multiplies 2^M × 3^M and 3^M × 2^M sparse matrices with O(5^M) and O(4^M) nonzeroes in O(5^M · poly(M)) operations.
  • C.2 The algorithm: The decomposition maps columns and rows of the original matrices to nonzero columns and rows of structured products using inverse minors.
  • C.2 The algorithm: The construction explicitly multiplies matrices of dimensions 2^(4M/5) × 2^(M/5) × 2^(4M/5) in 5^M · poly(M) operations.
  • C.2 The algorithm: Trace symmetries yield additional partial multiplication procedures, including Algorithms 2 and 3, which are then combined by tensorization.
  • C.2 The algorithm: Tensorization gives a 5^M × 4^(2M/5) × 5^M multiplication algorithm in 5^(2M) · poly(M) time over fields with 2^poly(M) elements.
Loading 1312.6680v2…