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

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

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

• 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
• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 5485574 (Why is no real title available?)
• 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

(63)

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

Describes a project that uses

Uses Software

• SuLQ
• GotoBLAS

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)