Deterministic APSP, Orthogonal Vectors, and More

Timothy M. Chan, R. Ryan Williams

Research output: Contribution to journalArticlepeer-review

Abstract

We show how to solve all-pairs shortest paths on n nodes in deterministic n3>/2>ω (s log n) time, and how to count the pairs of orthogonal vectors among n 0-1 vectors in d = clog n dimensions in deterministic n2-1/O(log c) time. These running times essentially match the best known randomized algorithms of Williams [46] and Abboud, Williams, and Yu [8], 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 deterministically count k-satisfiability (k-SAT) assignments on n variable formulas in 2n-n/O(k) time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam [24]. A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials.

Original languageEnglish (US)
Article number3402926
JournalACM Transactions on Algorithms
Volume17
Issue number1
DOIs
StatePublished - Jan 2021

Keywords

  • All-pairs shortest paths
  • derandomization
  • polynomial method
  • satisfiability

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Deterministic APSP, Orthogonal Vectors, and More'. Together they form a unique fingerprint.

Cite this