Faster All-Pairs Shortest Paths via Circuit Complexity (Q4554074)

scientific article; zbMATH DE number 6974578

Language	Label	Description	Also known as
English	Faster All-Pairs Shortest Paths via Circuit Complexity	scientific article; zbMATH DE number 6974578

Statements

instance of

scholarly article

0 references

title

Faster All-Pairs Shortest Paths via Circuit Complexity (English)

0 references

published in

SIAM Journal on Computing

0 references

publication date

7 November 2018

0 references

zbMATH Keywords

all-pairs shortest paths

0 references

graph algorithms

0 references

circuit complexity

0 references

matrix multiplication

0 references

tropical matrix multiplication

0 references

author

R. Ryan Williams

0 references

describes a project that uses

Algorithm 97

0 references

GotoBLAS

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

A Uniform Circuit Lower Bound for the Permanent

0 references

On the exponent of all pairs shortest path problem

0 references

Q4091421

0 references

Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made

0 references

\(\Sigma_ 1^ 1\)-formulae on finite structures

0 references

More Applications of the Polynomial Method to Algorithm Design

0 references

Finding and counting given length cycles

0 references

Necklaces, convolutions, and \(X+Y\)

0 references

Graph Expansion Analysis for Communication Costs of Fast Rectangular Matrix Multiplication

0 references

Subquadratic algorithms for 3SUM

0 references

POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD

0 references

Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)

0 references

On ACC

0 references

Q2913804

0 references

Unbounded fan-in circuits and associative functions

0 references

Speeding up the Four Russians Algorithm by About One More Logarithmic Factor

0 references

All-pairs shortest paths for unweighted undirected graphs in <i>o</i> ( <i>mn</i> ) time

0 references

All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time

0 references

More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

0 references

Rapid Multiplication of Rectangular Matrices

0 references

Constant Depth Reducibility

0 references

Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky

0 references

Adaptive Winograd's matrix multiplications

0 references

A more efficient algorithm for the min-plus multiplication

0 references

New Bounds on the Complexity of the Shortest Path Problem

0 references

Parity, circuits, and the polynomial-time hierarchy

0 references

Fibonacci heaps and their uses in improved network optimization algorithms

0 references

On a class of \(O(n^ 2)\) problems in computational geometry

0 references

Improved algorithm for all pairs shortest paths

0 references

An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path

0 references

Threshold circuits of bounded depth

0 references

An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths

0 references

Efficient Algorithms for Shortest Paths in Sparse Networks

0 references

A faster algorithm computing string edit distances

0 references

Q4856179

0 references

Efficient determination of the transitive closure of a directed graph

0 references

The bit-operation complexity of matrix multiplication and of all pair shortest path problem

0 references

A new approach to all-pairs shortest paths on real-weighted graphs

0 references

A Shortest Path Algorithm for Real-Weighted Undirected Graphs

0 references

Towards polynomial lower bounds for dynamic problems

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

Shortest-path problem is not harder than matrix multiplication

0 references

On the all-pairs-shortest-path problem in unweighted undirected graphs.

0 references

Preprocessing chains for fast dihedral rotations is hard or even impossible.

0 references

Gaussian elimination is not optimal

0 references

Simulation of Parallel Random Access Machines by Circuits

0 references

Computing and Combinatorics

0 references

An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem

0 references

A new upper bound on the complexity of the all pairs shortest path problem

0 references

Subcubic cost algorithms for the all pairs shortest path problem

0 references

Finding, Minimizing, and Counting Weighted Subgraphs

0 references

A Theorem on Boolean Matrices

0 references

Q3299223

0 references

New algorithms and lower bounds for circuits with linear threshold gates

0 references

Nonuniform ACC Circuit Lower Bounds

0 references

An improved combinatorial algorithm for Boolean matrix multiplication

0 references

All pairs shortest paths using bridging sets and rectangular matrix multiplication

0 references

Algorithms and Computation

0 references

full work available at URL

https://doi.org/10.1137/15m1024524

0 references

Identifiers

zbMATH Open document ID

1400.05075

0 references

DOI

10.1137/15M1024524

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4554074