Faster all-pairs shortest paths via circuit complexity
From MaRDI portal
Publication:4554074
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
- scientific article; zbMATH DE number 219247
- A new upper bound on the complexity of the all pairs shortest path problem
Cites work
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- A Shortest Path Algorithm for Real-Weighted Undirected Graphs
- A Theorem on Boolean Matrices
- A Uniform Circuit Lower Bound for the Permanent
- A faster algorithm computing string edit distances
- A more efficient algorithm for the min-plus multiplication
- A new approach to all-pairs shortest paths on real-weighted graphs
- A new upper bound on the complexity of the all pairs shortest path problem
- Adaptive Winograd's matrix multiplications
- Algorithms and Computation
- All pairs shortest paths using bridging sets and rectangular matrix multiplication
- All-pairs shortest paths for unweighted undirected graphs in \(o(mn)\) time
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- An \(O(n ^{3} \log\log n/\log ^{2} n)\) time algorithm for all pairs shortest paths
- An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
- An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
- Computing and Combinatorics
- Constant Depth Reducibility
- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Efficient Algorithms for Shortest Paths in Sparse Networks
- Efficient determination of the transitive closure of a directed graph
- Fibonacci heaps and their uses in improved network optimization algorithms
- Finding and counting given length cycles
- Finding, minimizing, and counting weighted subgraphs
- Gaussian elimination is not optimal
- Graph expansion analysis for communication costs of fast rectangular matrix multiplication
- Improved algorithm for all pairs shortest paths
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
- More applications of the polynomial method to algorithm design
- Necklaces, convolutions, and \(X+Y\)
- New Bounds on the Complexity of the Shortest Path Problem
- Nonuniform ACC circuit lower bounds
- On ACC
- On a class of \(O(n^ 2)\) problems in computational geometry
- On the all-pairs-shortest-path problem in unweighted undirected graphs.
- On the exponent of all pairs shortest path problem
- POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
- Parity, circuits, and the polynomial-time hierarchy
- Preprocessing chains for fast dihedral rotations is hard or even impossible.
- Rapid Multiplication of Rectangular Matrices
- Regularity lemmas and combinatorial algorithms
- Shortest-path problem is not harder than matrix multiplication
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Simulation of Parallel Random Access Machines by Circuits
- Speeding up the four Russians algorithm by about one more logarithmic factor
- Subcubic cost algorithms for the all pairs shortest path problem
- Subquadratic algorithms for 3SUM
- The bit-operation complexity of matrix multiplication and of all pair shortest path problem
- The polynomial method in circuit complexity applied to algorithm design (invited talk)
- Threshold circuits of bounded depth
- Towards polynomial lower bounds for dynamic problems
- Unbounded fan-in circuits and associative functions
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(27)- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- A robust version of Hegedűs's lemma, with applications
- scientific article; zbMATH DE number 7563818 (Why is no real title available?)
- On the hardness of approximate and exact (bichromatic) maximum inner product
- Efficient parameterized algorithms for computing all-pairs shortest paths
- How fast can we play Tetris greedily with rectangular pieces?
- A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
- scientific article; zbMATH DE number 7651168 (Why is no real title available?)
- Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
- 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
- Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter
- Faster all-pairs shortest paths via circuit complexity
- R-Kleene: a high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks
- A polyhedral perspective on tropical convolutions
- scientific article; zbMATH DE number 219247 (Why is no real title available?)
- More on change-making and related problems
- On \(\Delta\)-modular integer linear problems in the canonical form and equivalent problems
- Improved bounds for rectangular monotone min-plus product and applications
- Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
- Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
- From circuit complexity to faster all-pairs shortest paths
- The grid based approach, a fast local evaluation technique for line planning
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 Q4554074)
