Faster All-Pairs Shortest Paths via Circuit Complexity (Q4554074): Difference between revisions

@@ Property / author @@
-R. Ryan Williams
@@ Property / author: R. Ryan Williams / rank @@
-Normal rank
@@ Property / author @@
+R. Ryan Williams
@@ Property / author: R. Ryan Williams / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+Algorithm 97
@@ Property / describes a project that uses: Algorithm 97 / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+GotoBLAS
@@ Property / describes a project that uses: GotoBLAS / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+A Uniform Circuit Lower Bound for the Permanent
@@ Property / cites work: A Uniform Circuit Lower Bound for the Permanent / rank @@
+Normal rank
@@ Property / cites work @@
+On the exponent of all pairs shortest path problem
+Normal rank
@@ Property / cites work @@
+Q4091421
@@ Property / cites work: Q4091421 / rank @@
+Normal rank
@@ Property / cites work @@
+Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+More Applications of the Polynomial Method to Algorithm Design
+Normal rank
@@ Property / cites work @@
+Finding and counting given length cycles
@@ Property / cites work: Finding and counting given length cycles / rank @@
+Normal rank
@@ Property / cites work @@
+Necklaces, convolutions, and \(X+Y\)
@@ Property / cites work: Necklaces, convolutions, and \(X+Y\) / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication
+Normal rank
@@ Property / cites work @@
+Subquadratic algorithms for 3SUM
@@ Property / cites work: Subquadratic algorithms for 3SUM / rank @@
+Normal rank
@@ Property / cites work @@
+POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
+Normal rank
@@ Property / cites work @@
+Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
+Normal rank
@@ Property / cites work @@
+On ACC
@@ Property / cites work: On ACC / rank @@
+Normal rank
@@ Property / cites work @@
+Q2913804
@@ Property / cites work: Q2913804 / rank @@
+Normal rank
@@ Property / cites work @@
+Unbounded fan-in circuits and associative functions
+Normal rank
@@ Property / cites work @@
+Speeding up the Four Russians Algorithm by About One More Logarithmic Factor
+Normal rank
@@ Property / cites work @@
+All-pairs shortest paths for unweighted undirected graphs in             <i>o</i>             (             <i>mn</i>             ) time
+Normal rank
@@ Property / cites work @@
+All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
+Normal rank
@@ Property / cites work @@
+More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
+Normal rank
@@ Property / cites work @@
+Rapid Multiplication of Rectangular Matrices
@@ Property / cites work: Rapid Multiplication of Rectangular Matrices / rank @@
+Normal rank
@@ Property / cites work @@
+Constant Depth Reducibility
@@ Property / cites work: Constant Depth Reducibility / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
+Normal rank
@@ Property / cites work @@
+Adaptive Winograd's matrix multiplications
@@ Property / cites work: Adaptive Winograd's matrix multiplications / rank @@
+Normal rank
@@ Property / cites work @@
+A more efficient algorithm for the min-plus multiplication
+Normal rank
@@ Property / cites work @@
+New Bounds on the Complexity of the Shortest Path Problem
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Fibonacci heaps and their uses in improved network optimization algorithms
+Normal rank
@@ Property / cites work @@
+On a class of \(O(n^ 2)\) problems in computational geometry
+Normal rank
@@ Property / cites work @@
+Improved algorithm for all pairs shortest paths
@@ Property / cites work: Improved algorithm for all pairs shortest paths / rank @@
+Normal rank
@@ Property / cites work @@
+An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
+Normal rank
@@ Property / cites work @@
+Threshold circuits of bounded depth
@@ Property / cites work: Threshold circuits of bounded depth / rank @@
+Normal rank
@@ Property / cites work @@
+An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths
+Normal rank
@@ Property / cites work @@
+Efficient Algorithms for Shortest Paths in Sparse Networks
+Normal rank
@@ Property / cites work @@
+A faster algorithm computing string edit distances
+Normal rank
@@ Property / cites work @@
+Q4856179
@@ Property / cites work: Q4856179 / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient determination of the transitive closure of a directed graph
+Normal rank
@@ Property / cites work @@
+The bit-operation complexity of matrix multiplication and of all pair shortest path problem
+Normal rank
@@ Property / cites work @@
+A new approach to all-pairs shortest paths on real-weighted graphs
+Normal rank
@@ Property / cites work @@
+A Shortest Path Algorithm for Real-Weighted Undirected Graphs
+Normal rank
@@ Property / cites work @@
+Towards polynomial lower bounds for dynamic problems
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Shortest-path problem is not harder than matrix multiplication
+Normal rank
@@ Property / cites work @@
+On the all-pairs-shortest-path problem in unweighted undirected graphs.
+Normal rank
@@ Property / cites work @@
+Preprocessing chains for fast dihedral rotations is hard or even impossible.
+Normal rank
@@ Property / cites work @@
+Gaussian elimination is not optimal
@@ Property / cites work: Gaussian elimination is not optimal / rank @@
+Normal rank
@@ Property / cites work @@
+Simulation of Parallel Random Access Machines by Circuits
+Normal rank
@@ Property / cites work @@
+Computing and Combinatorics
@@ Property / cites work: Computing and Combinatorics / rank @@
+Normal rank
@@ Property / cites work @@
+An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
+Normal rank
@@ Property / cites work @@
+A new upper bound on the complexity of the all pairs shortest path problem
+Normal rank
@@ Property / cites work @@
+Subcubic cost algorithms for the all pairs shortest path problem
+Normal rank
@@ Property / cites work @@
+Finding, Minimizing, and Counting Weighted Subgraphs
+Normal rank
@@ Property / cites work @@
+A Theorem on Boolean Matrices
@@ Property / cites work: A Theorem on Boolean Matrices / rank @@
+Normal rank
@@ Property / cites work @@
+Q3299223
@@ Property / cites work: Q3299223 / rank @@
+Normal rank
@@ Property / cites work @@
+New algorithms and lower bounds for circuits with linear threshold gates
+Normal rank
@@ Property / cites work @@
+Nonuniform ACC Circuit Lower Bounds
@@ Property / cites work: Nonuniform ACC Circuit Lower Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+An improved combinatorial algorithm for Boolean matrix multiplication
+Normal rank
@@ Property / cites work @@
+All pairs shortest paths using bridging sets and rectangular matrix multiplication
+Normal rank
@@ Property / cites work @@
+Algorithms and Computation
@@ Property / cites work: Algorithms and Computation / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/15m1024524
+Normal rank
@@ Property / OpenAlex ID @@
+W2898839814
@@ Property / OpenAlex ID: W2898839814 / rank @@
+Normal rank