Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky

DOI10.1137/1.9781611974331.ch87zbMath1410.68286OpenAlexW4242600797MaRDI QIDQ4575668

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

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

Related Items (32)

Faster All-Pairs Shortest Paths via Circuit Complexity ⋮ An \(O(n^3 \log \log n / \log^2 n)\) time algorithm for all pairs shortest paths ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Unnamed Item ⋮ Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back ⋮ An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs ⋮ Unnamed Item ⋮ Structured \((\min ,+)\)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Solving non-linear Boolean equation systems by variable elimination ⋮ Smallest \(k\)-enclosing rectangle revisited ⋮ Unnamed Item ⋮ Smallest k-enclosing rectangle revisited ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ The Orthogonal Vectors Conjecture for Branching Programs and Formulas ⋮ Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ On Super Strong ETH ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ From Circuit Complexity to Faster All-Pairs Shortest Paths ⋮ Unnamed Item ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Dominance Product and High-Dimensional Closest Pair under L_infty ⋮ Average-case rigidity lower bounds

This page was built for publication: Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky