Faster all-pairs shortest paths via circuit complexity

DOI10.1145/2591796.2591811zbMATH Open1315.68282arXiv1312.6680OpenAlexW2064790310WikidataQ56078256 ScholiaQ56078256MaRDI QIDQ5259602FDOQ5259602

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)

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of Cryptography
• The geometry of differential privacy: the small database and approximate cases
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• On the complexity of differentially private data release
• Collusion-secure fingerprinting for digital data
• Advances in Cryptology – CRYPTO 2004
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Characterizing the sample complexity of private learners
• Faster Algorithms for Privately Releasing Marginals
• Faster private release of marginals on small databases
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately releasing conjunctions and the statistical query barrier
• Efficient algorithms for privately releasing marginals via convex relaxations

Cited In (47)

• A Sparsified Four-Russian Algorithm for RNA Folding
• Improved distance queries and cycle counting by Frobenius normal form
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Subquadratic algorithms for succinct stable matching
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
• Directed shortest paths via approximate cost balancing
• Constant-Round Interactive Proof Systems for AC0[2] and NC1
• Smallest k-enclosing rectangle revisited
• Quantum Complexity of Boolean Matrix Multiplication and Related Problems
• A \#SAT algorithm for small constant-depth circuits with PTF gates
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)
• Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
• \((\min ,+)\) matrix and vector products for inputs decomposable into few monotone subsequences
• Near-linear time approximation schemes for geometric maximum coverage
• Smallest \(k\)-enclosing rectangle revisited
• A spectral approach to the shortest path problem
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Title not available (Why is that?)
• Minimax regret 1-sink location problem with accessibility in dynamic general networks
• A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
• Title not available (Why is that?)
• Average-case complexity of the min-sum matrix product problem
• Linear Time Approximation Schemes for Geometric Maximum Coverage
• Title not available (Why is that?)
• Efficient single-pair all-shortest-path query processing for massive dynamic networks
• Anti-concentration for polynomials of independent random variables
• Title not available (Why is that?)
• An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths
• Fine-Grained Complexity Theory (Tutorial)
• Improved bounds for rectangular monotone min-plus product and applications
• Approximating the minimum cycle mean
• Title not available (Why is that?)
• Title not available (Why is that?)
• The idemetric property: when most distances are (almost) the same
• Algebraic methods in the congested clique
• If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
• Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time
• Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs
• 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

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)