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

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 n²−^ε1/2+O(δ⁾ for nearest neighbors, or n²−Ω(√ε/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 n²−Ω(^ε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−Ω(ε¹/³/log²/³(1/ε)) . As one application, we obtain improved deterministic and randomized (1+ε)-approximation algorithms for MAX-SAT.