Faster all-pairs shortest paths via circuit complexity

DOI10.1145/2591796.2591811MaRDI QIDQ5259602zbMATH OpenOpenAlexWikidataFDO

Authors Ryan Williams

Publication date 26 June 2015

Published in Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.6680

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two $nimesn$ 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^{Omega(log n)^{1/2}}}] and is correct with high probability. On the word RAM, the algorithm runs in $n^3/2^{Omega(logn{)}^{1/2}}+n^{2+o(1)}logM$ time for edge weights in $([0,M]capmathbbZ)cupinfty$. Prior algorithms used either $n^3/(lo{g}^{c}n)$ time for various $cleq2$, or $$ time for various $alpha>0$ and $$. The new algorithm applies a tool from circuit complexity, namely the Razborov-Smolensky polynomials for approximately representing ${sfAC}^0[p]$ circuits, to efficiently reduce a matrix product over the $(min,+)$ algebra to a relatively small number of rectangular matrix products over ${mathbbF}_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^{lo{g}^{delta}n}$ time for some $delta>0$, which utilizes the Yao-Beigel-Tarui translation of ${sfAC}^0[m]$ circuits into "nice" depth-two circuits.

Recommendations

• Faster all-pairs shortest paths via circuit complexity
• From circuit complexity to faster all-pairs shortest paths
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• scientific article; zbMATH DE number 219247

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• Advances in Cryptology – CRYPTO 2004
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Collusion-secure fingerprinting for digital data
• Differential privacy and the fat-shattering dimension of linear queries
• Efficient algorithms for privately releasing marginals via convex relaxations
• Faster algorithms for privately releasing marginals
• Faster private release of marginals on small databases
• Interactive privacy via the median mechanism
• Iterative Constructions and Private Data Release
• Lower bounds in differential privacy
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• On the complexity of differentially private data release, efficient algorithms and hardness results
• On the geometry of differential privacy
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Theory of Cryptography

Cited in

(52)

• Improved distance queries and cycle counting by Frobenius normal form
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• scientific article; zbMATH DE number 7561539 (Why is no real title available?)
• Subcubic equivalences between path, matrix, and triangle problems
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
• Directed shortest paths via approximate cost balancing
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• Tighter connections between Formula-SAT and shaving logs
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Smallest k-enclosing rectangle revisited
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• scientific article; zbMATH DE number 7561512 (Why is no real title available?)
• scientific article; zbMATH DE number 7559066 (Why is no real title available?)
• Faster all-pairs shortest paths via circuit complexity
• Near-linear time approximation schemes for geometric maximum coverage
• \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
• If the current clique algorithms are optimal, so is Valiant's parser
• More applications of the polynomial method to algorithm design
• Smallest \(k\)-enclosing rectangle revisited
• A spectral approach to the shortest path problem
• A sparsified Four-Russian algorithm for RNA folding
• Tensor network complexity of multilinear maps
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Minimax regret 1-sink location problem with accessibility in dynamic general networks
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• scientific article; zbMATH DE number 7561506 (Why is no real title available?)
• A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
• Average-case complexity of the min-sum matrix product problem
• scientific article; zbMATH DE number 219247 (Why is no real title available?)
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• A New Combinatorial Approach for Sparse Graph Problems
• Efficient single-pair all-shortest-path query processing for massive dynamic networks
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• Anti-concentration for polynomials of independent random variables
• scientific article; zbMATH DE number 7250154 (Why is no real title available?)
• An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
• Improved bounds for rectangular monotone min-plus product and applications
• Approximating the minimum cycle mean
• Fine-Grained Complexity Theory (Tutorial)
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)
• The idemetric property: when most distances are (almost) the same
• From circuit complexity to faster all-pairs shortest paths
• Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs
• Approximating APSP without scaling: equivalence of approximate min-plus and exact min-max
• Quantum complexity of Boolean matrix multiplication and related problems
• A new coding-based algorithm for finding closest pair of vectors
• Hardness of RNA folding problem with four symbols
• Percolation centrality via Rademacher Complexity
• Efficient indexes for jumbled pattern matching with constant-sized alphabet

Describes a project that uses

Uses Software

• GotoBLAS
• SuLQ

This page was built for publication: Faster all-pairs shortest paths via circuit complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259602)