| dc.contributor |
Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
|
| dc.contributor |
Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
|
| dc.creator |
Alman, Joshua |
|
| dc.creator |
Williams, R Ryan |
|
| dc.date |
2021-04-09T13:04:20Z |
|
| dc.date |
2021-04-09T13:04:20Z |
|
| dc.date |
2020-01 |
|
| dc.date |
2021-04-08T14:25:22Z |
|
| dc.date.accessioned |
2023-03-01T18:11:41Z |
|
| dc.date.available |
2023-03-01T18:11:41Z |
|
| dc.identifier |
https://hdl.handle.net/1721.1/130425 |
|
| dc.identifier |
Alman, Josh et al. “Faster deterministic and Las vegas algorithms for offline approximate nearest neighbors in high dimensions.” Paper in the Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Salt Lake City, Utah, January 5 - 8, 2020, Association for Computing Machinery: 637-649 © 2020 The Author(s) |
|
| dc.identifier.uri |
http://localhost:8080/xmlui/handle/CUHPOERS/279105 |
|
| dc.description |
We present a deterministic, truly subquadratic algorithm for offline (1 + ε)-approximate nearest or farthest neighbor search (in particular, the closest pair or diameter problem) in Hamming space in any dimension d ≤ nδ, for a sufficiently small constant δ > 0. The running time of the algorithm is roughly n2−ε1/2+O(δ) for nearest neighbors, or n2−Ω(√ε/log(1/ε)) for farthest. The algorithm follows from a simple combination of expander walks, Chebyshev polynomials, and rectangular matrix multiplication. We also show how to eliminate errors in the previous Monte Carlo randomized algorithm of Alman, Chan, and Williams [FOCS'16] for offline approximate nearest or farthest neighbors, and obtain a Las Vegas randomized algorithm with expected running time n2−Ω(ε1/3/log(1/ε)) . Finally, we note a simplification of Alman, Chan, and Williams' method and obtain a slightly improved Monte Carlo randomized algorithm with running time n2−Ω(ε1/3/log2/3(1/ε)) . As one application, we obtain improved deterministic and randomized (1+ε)-approximation algorithms for MAX-SAT. |
|
| dc.description |
National Science Foundation (U.S.) (Grants CCF-1651838, CCF-1741615) |
|
| dc.format |
application/pdf |
|
| dc.language |
en |
|
| dc.publisher |
Association for Computing Machinery |
|
| dc.relation |
10.1137/1.9781611975994.39 |
|
| dc.relation |
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
|
| dc.rights |
Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. |
|
| dc.source |
SIAM |
|
| dc.title |
Faster deterministic and Las vegas algorithms for offline approximate nearest neighbors in high dimensions |
|
| dc.type |
Article |
|
| dc.type |
http://purl.org/eprint/type/ConferencePaper |
|