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 |