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

DOI10.1137/1.9781611974331.CH87MaRDI QIDQ4575668zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Ryan Williams

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

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)

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

Cited in

(36)

• Satisfiability and derandomization for small polynomial threshold circuits
• 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
• scientific article; zbMATH DE number 7651219 (Why is no real title available?)
• Average-case rigidity lower bounds
• Smallest k-enclosing rectangle revisited
• scientific article; zbMATH DE number 7561512 (Why is no real title available?)
• scientific article; zbMATH DE number 7559066 (Why is no real title available?)
• 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
• Smallest \(k\)-enclosing rectangle revisited
• scientific article; zbMATH DE number 7561744 (Why is no real title available?)
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• An O(n^3 n / ^2 n) time algorithm for all pairs shortest paths
• Towards permissionless consensus in the standard model via fine-grained complexity
• scientific article; zbMATH DE number 7561569 (Why is no real title available?)
• From circuit complexity to faster all-pairs shortest paths
• Counting solutions to polynomial systems via reductions
• Solving non-linear Boolean equation systems by variable elimination
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
• The fine-grained complexity of multi-dimensional ordering properties

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)