209 citations · 414 across the 29 of their papers we have counts for
37 papers
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 queries. Primarily, for the high-di…
Data Structures for Density Estimation
Anders Aamand, Alexandr Andoni, Justin Y. Chen +3
We study statistical/computational tradeoffs for the following density estimation problem: given distributions over a discrete domain of size , and sampli…
Communication Complexity of Inner Product in Symmetric Normed Spaces
Alexandr Andoni, Jarosław Błasiok, Arnold Filtser
We introduce and study the communication complexity of computing the inner product of two vectors, where the input is restricted w.r.t. a norm on the space . Here…
Estimating the Longest Increasing Subsequence in Nearly Optimal Time
Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha +1
Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length can be computed exactly i…
Learning to Hash Robustly, Guaranteed
Alexandr Andoni, Daniel Beaglehole
The indexing algorithms for the high-dimensional nearest neighbor search (NNS) with the best worst-case guarantees are based on the randomized Locality Sensitive Hashing (LSH), and…
From Average Embeddings To Nearest Neighbor Search
Alexandr Andoni, David Cheikhi
In this note, we show that one can use average embeddings, introduced recently in [Naor'20, arXiv:1905.01280], to obtain efficient algorithms for approximate nearest neighbor searc…