Optimal Las Vegas Approximate Near Neighbors in ${\ell }_p$

Alexander Wei

We show that approximate near neighbor search in high dimensions can be solved in a Las Vegas fashion (i.e., without false negatives) for ${\ell }_p$ ($1\le p\le 2$) while matching th…