Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
© 2020 ACM. 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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143937 |
| _version_ | 1826199328710983680 |
|---|---|
| author | Chan, Timothy M Williams, R Ryan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Chan, Timothy M Williams, R Ryan |
| author_sort | Chan, Timothy M |
| collection | MIT |
| description | © 2020 ACM. 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. |
| first_indexed | 2024-09-23T11:18:05Z |
| format | Article |
| id | mit-1721.1/143937 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:18:05Z |
| publishDate | 2022 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1439372023-02-06T15:57:43Z Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky Chan, Timothy M Williams, R Ryan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2020 ACM. 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. 2022-07-21T16:27:28Z 2022-07-21T16:27:28Z 2021 2022-07-21T16:17:16Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/143937 Chan, Timothy M and Williams, R Ryan. 2021. "Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky." ACM Transactions on Algorithms, 17 (1). en 10.1145/3402926 ACM Transactions on Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) other univ website |
| spellingShingle | Chan, Timothy M Williams, R Ryan Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky |
| title | Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky |
| title_full | Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky |
| title_fullStr | Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky |
| title_full_unstemmed | Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky |
| title_short | Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky |
| title_sort | deterministic apsp orthogonal vectors and more quickly derandomizing razborov smolensky |
| url | https://hdl.handle.net/1721.1/143937 |
| work_keys_str_mv | AT chantimothym deterministicapsporthogonalvectorsandmorequicklyderandomizingrazborovsmolensky AT williamsrryan deterministicapsporthogonalvectorsandmorequicklyderandomizingrazborovsmolensky |