Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky

Timothy M. Chan, Ryan Williams

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show how to solve all-pairs shortest paths on n nodes in deterministic n3/2ω(√logn) time, and how to count the pairs of orthogonal vectors among n 0-1 vectors in d = clogn dimensions in deterministic n2-1/o(logc) time. These running times essentially match the best known randomized algorithms of (Williams, STOC' 14) and (Abboud, Williams, and Yu, SODA 2015) respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to de-terministically count fc-SAT assignments on n variable formulas in 2n-n/o(k) tjme roUghly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam (2013). A key to our constructions is an efficient way to determinis-tically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials.

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages1246-1255
Number of pages10
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Externally publishedYes
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume2

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
CountryUnited States
CityArlington
Period1/10/161/12/16

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky'. Together they form a unique fingerprint.

Cite this