Deterministic APSP, Orthogonal Vectors, and More
From MaRDI portal
Publication:5028339
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
(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)
