@article{4b25cecdfe0a47e0a1422d10b74c2019,
title = "Deterministic APSP, Orthogonal Vectors, and More",
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.",
keywords = "All-pairs shortest paths, derandomization, polynomial method, satisfiability",
author = "Chan, {Timothy M.} and Williams, {R. Ryan}",
note = "Funding Information: A preliminary version of this article appeared in SODA, 2016. This work was completed while the first author was at the University of Waterloo. It was supported in part by NSF CCF-1814026. This work was completed while the second author was at Stanford University, supported in part by a David Morgenthaler II Faculty Fellowship, a Sloan Fellowship, and NSF CCF-1212372. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. Authors{\textquoteright} addresses: T. M. Chan, Department of Computer Science, University of Illinois at Urbana-Champaign, 201 N. Goodwin Ave., Urbana, IL, 61801; email: tmc@illinois.edu; R. R. Williams, CSAIL and Department of Electrical Engineering and Computer Science, MIT, 32 Vassar St., Cambridge, MA, 02139; email: rrw@mit.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. {\textcopyright} 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1549-6325/2020/12-ART2 $15.00 https://doi.org/10.1145/3402926 Publisher Copyright: {\textcopyright} 2020 ACM.",
year = "2021",
month = jan,
doi = "10.1145/3402926",
language = "English (US)",
volume = "17",
journal = "ACM Transactions on Algorithms",
issn = "1549-6325",
publisher = "Association for Computing Machinery (ACM)",
number = "1",
}