Efficient Algorithms for Adversarially Robust Approximate Nearest Neighbor Search

Alexandr Andoni, Themistoklis Haris, Esty Kelman +1

We study the Approximate Nearest Neighbor (ANN) problem under a powerful adaptive adversary that controls both the dataset and a sequence of $Q$ queries. Primarily, for the high-di…