Publications (26)
Optimal Data-Dependent Hashing for Approximate Near Neighbors
Alexandr Andoni, Ilya Razenshteyn
Streaming Algorithms from Precision Sampling
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
Snowflake universality of Wasserstein spaces
Alexandr Andoni, Assaf Naor, Ofer Neiman
Approximating Edit Distance in Near-Linear Time
Alexandr Andoni, Krzysztof Onak
Beyond Locality-Sensitive Hashing
Alexandr Andoni, Piotr Indyk, Huy L. Nguyen +1
Approximate Near Neighbors for General Symmetric Norms
Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov +2
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing
Alexandr Andoni, Ilya Razenshteyn
Subspace Embedding and Linear Regression with Orlicz Norm
Alexandr Andoni, Chengyu Lin, Ying Sheng +2
Practical and Optimal LSH for Angular Distance
Alexandr Andoni, Piotr Indyk, Thijs Laarhoven +2
The Sketching Complexity of Graph Cuts
Alexandr Andoni, Robert Krauthgamer, David P. Woodruff
Sketching and Embedding are Equivalent for Norms
Alexandr Andoni, Robert Krauthgamer, Ilya Razenshteyn
Parallel Algorithms for Geometric Graph Problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak +1
Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni, Clifford Stein, Zhao Song +2
Global Alignment of Molecular Sequences via Ancestral State Reconstruction
Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim +1
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak
A Differential Equations Approach to Optimizing Regret Trade-offs
Alexandr Andoni, Rina Panigrahy
Spectral Approaches to Nearest Neighbor Search
Amirali Abdullah, Alexandr Andoni, Ravindran Kannan +1
Better Bounds for Frequency Moments in Random-Order Streams
Alexandr Andoni, Andrew McGregor, Krzysztof Onak +1
Batch Sparse Recovery, or How to Leverage the Average Sparsity
Alexandr Andoni, Lior Kamma, Robert Krauthgamer +1
Approximate Nearest Neighbor Search in High Dimensions
Alexandr Andoni, Piotr Indyk, Ilya Razenshteyn
Towards (1+ε)-Approximate Flow Sparsifiers
Alexandr Andoni, Anupam Gupta, Robert Krauthgamer
Tight Lower Bound for Linear Sketches of Moments
Alexandr Andoni, Huy L. Nguyen, Yury Polyanskiy +1
Coding sets with asymmetric information
Alexandr Andoni, Javad Ghaderi, Daniel Hsu +2
Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn +1
Log Diameter Rounds Algorithms for $2$-Vertex and $2$-Edge Connectivity
Alexandr Andoni, Clifford Stein, Peilin Zhong
Two Party Distribution Testing: Communication and Security
Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki