From Circuit Complexity to Faster All-Pairs Shortest Paths

DOI10.1137/21M1418654zbMath1470.05139OpenAlexW3191901775MaRDI QIDQ5009891

R. Ryan Williams

Publication date: 9 August 2021

Published in: SIAM Review (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/21m1418654

zbMATH Keywords

graph algorithmscircuit complexitymatrix multiplicationall-pairs shortest pathstropical matrix multiplication

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Analytic circuit theory (94C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph operations (line graphs, products, etc.) (05C76)

Uses Software

• GotoBLAS
• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Necklaces, convolutions, and \(X+Y\)
• Finding and counting given length cycles
• An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Unbounded fan-in circuits and associative functions
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• A faster algorithm computing string edit distances
• Shortest-path problem is not harder than matrix multiplication
• The bit-operation complexity of matrix multiplication and of all pair shortest path problem
• A new upper bound on the complexity of the all pairs shortest path problem
• On ACC
• On the exponent of all pairs shortest path problem
• Subcubic cost algorithms for the all pairs shortest path problem
• Preprocessing chains for fast dihedral rotations is hard or even impossible.
• An improved combinatorial algorithm for Boolean matrix multiplication
• A new approach to all-pairs shortest paths on real-weighted graphs
• On a class of \(O(n^ 2)\) problems in computational geometry
• Threshold circuits of bounded depth
• Improved algorithm for all pairs shortest paths
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Subquadratic algorithms for 3SUM
• Gaussian elimination is not optimal
• Efficient determination of the transitive closure of a directed graph
• Finding, Minimizing, and Counting Weighted Subgraphs
• Towards polynomial lower bounds for dynamic problems
• An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
• Adaptive Winograd's matrix multiplications
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• All-pairs shortest paths for unweighted undirected graphs in o ( mn ) time
• Nonuniform ACC Circuit Lower Bounds
• Simulation of Parallel Random Access Machines by Circuits
• Parity, circuits, and the polynomial-time hierarchy
• Constant Depth Reducibility
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Rapid Multiplication of Rectangular Matrices
• A more efficient algorithm for the min-plus multiplication
• New Bounds on the Complexity of the Shortest Path Problem
• Efficient Algorithms for Shortest Paths in Sparse Networks
• A Uniform Circuit Lower Bound for the Permanent
• Threesomes, Degenerates, and Love Triangles
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• Tight Hardness Results for Maximum Weight Rectangles
• New algorithms and lower bounds for circuits with linear threshold gates
• Subcubic Equivalences Between Path, Matrix, and Triangle Problems
• Computing and Combinatorics
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
• Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
• Fibonacci heaps and their uses in improved network optimization algorithms
• Fine-grained complexity for sparse graphs
• A Shortest Path Algorithm for Real-Weighted Undirected Graphs
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• More Applications of the Polynomial Method to Algorithm Design
• Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
• Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• Algorithms and Computation
• A Theorem on Boolean Matrices

This page was built for publication: From Circuit Complexity to Faster All-Pairs Shortest Paths