Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky

DOI10.1137/1.9781611974331.CH87zbMATH Open1410.68286OpenAlexW4242600797MaRDI QIDQ4575668FDOQ4575668

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch87

Recommendations

From circuit complexity to faster all-pairs shortest paths
Faster all-pairs shortest paths via circuit complexity
Faster all-pairs shortest paths via circuit complexity
More applications of the polynomial method to algorithm design
Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions

Mathematics Subject Classification ID

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 (36)

Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
Dominance product and high-dimensional closest pair under \(L_\infty\)
Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
Title not available (Why is that?)
Smallest k-enclosing rectangle revisited
Average-case rigidity lower bounds
Title not available (Why is that?)
Title not available (Why is that?)
Faster all-pairs shortest paths via circuit complexity
The Orthogonal Vectors Conjecture for Branching Programs and Formulas
More applications of the polynomial method to algorithm design
Title not available (Why is that?)
Title not available (Why is that?)
Smallest \(k\)-enclosing rectangle revisited
Efficient Construction of Rigid Matrices Using an NP Oracle
Finding orthogonal vectors in discrete structures
Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
Deterministic APSP, Orthogonal Vectors, and More
On super strong ETH
A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
Towards hardness of approximation for polynomial time problems
An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs
Title not available (Why is that?)
Towards permissionless consensus in the standard model via fine-grained complexity
An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths
Title not available (Why is that?)
From circuit complexity to faster all-pairs shortest paths
Counting solutions to polynomial systems via reductions
Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
Solving non-linear Boolean equation systems by variable elimination
Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
The fine-grained complexity of multi-dimensional ordering properties
Satisfiability and derandomization for small polynomial threshold circuits

This page was built for publication: Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky

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