Deterministic APSP, Orthogonal Vectors, and More
From MaRDI portal
Publication:5028339
DOI10.1145/3402926OpenAlexW3115470548MaRDI QIDQ5028339FDOQ5028339
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)
Cited In (8)
- Directed shortest paths via approximate cost balancing
- CNF satisfiability in a subspace and related problems
- Improved Merlin-Arthur protocols for central problems in fine-grained complexity
- Computing generalized convolutions faster than brute force
- Parameterized complexity of diameter
- Rigid matrices from rectangular PCPs
- Finer-grained reductions in fine-grained hardness of approximation
- Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
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)
