Deterministic APSP, Orthogonal Vectors, and More

DOI10.1145/3402926MaRDI QIDQ5028339zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Ryan Williams

Publication date 8 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3402926

zbMATH Keywords

all-pairs shortest pathsderandomizationpolynomial methodsatisfiability

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• scientific article; zbMATH DE number 2187725
• A fast randomized algorithm for orthogonal projection
• A fast randomized algorithm for the approximation of matrices
• A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
• Fast nondeterministic matrix multiplication via derandomization of Freivalds' algorithm
• An exact correspondence of linear problems and randomizing linear algorithms
• Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x]\)
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• On the complexity of approximating extremal determinants in matrices

Cited in

(18)

• CNF satisfiability in a subspace and related problems
• Parameterized complexity of diameter
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• Computing generalized convolutions faster than brute force
• Rigid matrices from rectangular PCPs
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
• Directed shortest paths via approximate cost balancing
• Finer-grained reductions in fine-grained hardness of approximation
• Finer-grained reductions in fine-grained hardness of approximation
• A VLSI circuit model accounting for wire delay
• Towards stronger depth lower bounds
• Fast convolutions for near-convex sequences
• The complexity of diameter on H-free graphs
• Computing generalized convolutions faster than brute force
• On polynomial kernels for traveling salesperson problem and its generalizations
• The complexity of diameter on \(H\)-free graphs
• Quantum algorithms for Hopcroft's problem
• The planted orthogonal vectors problem

This page was built for publication: Deterministic APSP, Orthogonal Vectors, and More

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028339)