Hardness of Approximate Nearest Neighbor Search under L-infinity

Published in In submission, 2020

[arxiv]

Assuming SETH, we show the hardness of Approximate Nearest Neighbor Search (ANN) under the $\ell_\infty$ norm with two simple reductions. Our first reduction is from a special case of SVP, which captures many provably hard instances of the general case. Our second reduction improves the approximation factor for hardness, and shows that 3-approximation requires near-linear query time even with polynomial preprocessing time. Lastly, we show that approximation factor of 3 is a barrier for any naive gadget reduction from the Orthogonal Vectors problem.