Faster All-Pairs Shortest Paths via Circuit Complexity
From MaRDI portal
Publication:4554074
DOI10.1137/15M1024524zbMath1400.05075OpenAlexW2898839814MaRDI QIDQ4554074
Publication date: 7 November 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/15m1024524
graph algorithmscircuit complexitymatrix multiplicationall-pairs shortest pathstropical matrix multiplication
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76)
Related Items (17)
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ Improved bounds for rectangular monotone min-plus product and applications ⋮ How fast can we play Tetris greedily with rectangular pieces? ⋮ Unnamed Item ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ A polyhedral perspective on tropical convolutions ⋮ On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems ⋮ A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem ⋮ Unnamed Item ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees ⋮ More on change-making and related problems ⋮ Unnamed Item ⋮ The grid based approach, a fast local evaluation technique for line planning ⋮ Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
Uses Software
Cites Work
- 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
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- 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
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- New algorithms and lower bounds for circuits with linear threshold gates
- 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
- Fibonacci heaps and their uses in improved network optimization algorithms
- 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
- Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
- Algorithms and Computation
- A Theorem on Boolean Matrices
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Faster All-Pairs Shortest Paths via Circuit Complexity
