TY - GEN

T1 - Faster deterministic and Las vegas algorithms for offline approximate nearest neighbors in high dimensions

AU - Alman, Josh

AU - Chan, Timothy M.

AU - Williams, Ryan

N1 - Funding Information:
Work supported in part by NSF CCF-1651838 and NSF CCF-1741615. Work supported in part by NSF Grant CCF-1814026. Work supported in part by NSF Grant CCF-1741615.
Publisher Copyright:
Copyright © 2020 by SIAM

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85084093503&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85084093503&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85084093503

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 637

EP - 649

BT - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

A2 - Chawla, Shuchi

PB - Association for Computing Machinery

T2 - 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020

Y2 - 5 January 2020 through 8 January 2020

ER -