209 citations · 414 across the 29 of their papers we have counts for
33 papers · 1 filter
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…
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…
Streaming Complexity of SVMs
Alexandr Andoni, Collin Burns, Yi Li +2
We study the space complexity of solving the bias-regularized SVM problem in the streaming model. This is a classic supervised learning problem that has drawn lots of attention, in…