Hardness of Approximate Nearest Neighbor Search under L-infinity

Young Kun Ko, Min Jae Song

We show conditional hardness of Approximate Nearest Neighbor Search (ANN) under the ${\ell }_{\infty }$ norm with two simple reductions. Our first reduction shows that hardness of a spec…