Lower bounds for embedding edit distance into normed spaces. - Alexandr Andoni; Michel Deza; Anupam Gupta 001; Piotr Indyk; Sofya Raskhodnikova (SODA, 2003)

Graceful service degradation (or, how to know your payment is late). - Alexandr Andoni; Jessica Staddon (EC, 2005)

On the Optimality of the Dimensionality Reduction Method. - Alexandr Andoni; Piotr Indyk; Mihai Patrascu (FOCS, 2006)

Efficient algorithms for substring near neighbor problem. - Alexandr Andoni; Piotr Indyk (SODA, 2006)

The Computational Hardness of Estimating Edit Distance [Extended Abstract]. - Alexandr Andoni; Robert Krauthgamer (FOCS, 2007)

Testing k-wise and almost k-wise independence. - Noga Alon; Alexandr Andoni; Tali Kaufman; Kevin Matulef; Ronitt Rubinfeld; Ning Xie 002 (STOC, 2007)

Earth Mover Distance over High-Dimensional Spaces. - Alexandr Andoni; Piotr Indyk; Robert Krauthgamer (Electron. Colloquium Comput. Complex., 2007)

Hardness of Nearest Neighbor under L-infinity. - Alexandr Andoni; Dorian Croitoru; Mihai Patrascu (FOCS, 2008)

Corrigendum to "efficient similarity search and classification via rank aggregation" by Ronald Fagin, Ravi Kumar and D. Sivakumar (proc. SIGMOD'03). - Alexandr Andoni; Ronald Fagin; Ravi Kumar 001; Mihai Patrascu; D. Sivakumar 001 (SIGMOD Conference, 2008)

Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. - Alexandr Andoni; Piotr Indyk (Commun. ACM, 2008)

Better Bounds for Frequency Moments in Random-Order Streams - Alexandr Andoni; Andrew McGregor 001; Krzysztof Onak; Rina Panigrahy (CoRR, 2008)

Efficient Sketches for Earth-Mover Distance, with Applications. - Alexandr Andoni; Khanh Do Ba; Piotr Indyk; David P. Woodruff (FOCS, 2009)

External Sampling. - Alexandr Andoni; Piotr Indyk; Krzysztof Onak; Ronitt Rubinfeld (ICALP (1), 2009)

Overcoming the l1 non-embeddability barrier: algorithms for product metrics. - Alexandr Andoni; Piotr Indyk; Robert Krauthgamer (SODA, 2009)

Approximate line nearest neighbor in high dimensions. - Alexandr Andoni; Piotr Indyk; Robert Krauthgamer; Huy L. Nguyen (SODA, 2009)

NN search : the old, the new, and the impossible. - Alexandr Andoni (2009)

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. - Alexandr Andoni; Robert Krauthgamer; Krzysztof Onak (FOCS, 2010)

Global Alignment of Molecular Sequences via Ancestral State Reconstruction. - Alexandr Andoni; Constantinos Daskalakis; Avinatan Hassidim; Sébastien Roch (ICS, 2010)

Sublinear Algorithms in the External Memory Model. - Alexandr Andoni; Piotr Indyk; Krzysztof Onak; Ronitt Rubinfeld (Property Testing, 2010)

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. - Alexandr Andoni; Robert Krauthgamer; Krzysztof Onak (Property Testing, 2010)

Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. - Alexandr Andoni; T. S. Jayram; Mihai Patrascu (SODA, 2010)

Near-Optimal Sublinear Time Algorithms for Ulam Distance. - Alexandr Andoni; Huy L. Nguyen (SODA, 2010)

Streaming Algorithms from Precision Sampling - Alexandr Andoni; Robert Krauthgamer; Krzysztof Onak (CoRR, 2010)

The Computational Hardness of Estimating Edit Distance. - Alexandr Andoni; Robert Krauthgamer (SIAM J. Comput., 2010)

Near Linear Lower Bound for Dimension Reduction in L1. - Alexandr Andoni; Moses Charikar; Ofer Neiman; Huy L. Nguyen (FOCS, 2011)

Streaming Algorithms via Precision Sampling. - Alexandr Andoni; Robert Krauthgamer; Krzysztof Onak (FOCS, 2011)

Nearest Neighbor Search in High-Dimensional Spaces. - Alexandr Andoni (MFCS, 2011)

Approximating Edit Distance in Near-Linear Time. - Alexandr Andoni; Krzysztof Onak (SIAM J. Comput., 2012)

The smoothed complexity of edit distance. - Alexandr Andoni; Robert Krauthgamer (ACM Trans. Algorithms, 2012)

Tight Lower Bound for Linear Sketches of Moments. - Alexandr Andoni; Huy L. Nguyên; Yury Polyanskiy; Yihong Wu 001 (ICALP (1), 2013)

Shift Finding in Sub-Linear Time. - Alexandr Andoni; Piotr Indyk; Dina Katabi; Haitham Hassanieh (SODA, 2013)

Eigenvalues of a matrix in the streaming model. - Alexandr Andoni; Huy L. Nguyen (SODA, 2013)

Homomorphic fingerprints under misalignments: sketching edit and shift distances. - Alexandr Andoni; Assaf Goldberger; Andrew McGregor 001; Ely Porat (STOC, 2013)

Towards (1+ε)-Approximate Flow Sparsifiers. - Alexandr Andoni; Anupam Gupta 001; Robert Krauthgamer (CoRR, 2013)

A Differential Equations Approach to Optimizing Regret Trade-offs - Alexandr Andoni; Rina Panigrahy (CoRR, 2013)

Special Issue: APPROX-RANDOM 2012: Guest Editors' Foreword. - Alexandr Andoni; Atri Rudra (Theory Comput., 2013)

Spectral Approaches to Nearest Neighbor Search. - Amirali Abdullah; Alexandr Andoni; Ravindran Kannan; Robert Krauthgamer (FOCS, 2014)

Learning Polynomials with Neural Networks. - Alexandr Andoni; Rina Panigrahy; Gregory Valiant; Li Zhang 001 (ICML, 2014)

Towards (1 + ∊)-Approximate Flow Sparsifiers. - Alexandr Andoni; Anupam Gupta 001; Robert Krauthgamer (SODA, 2014)

Beyond Locality-Sensitive Hashing. - Alexandr Andoni; Piotr Indyk; Huy L. Nguyen; Ilya P. Razenshteyn (SODA, 2014)

Learning Sparse Polynomial Functions. - Alexandr Andoni; Rina Panigrahy; Gregory Valiant; Li Zhang 001 (SODA, 2014)

Parallel algorithms for geometric graph problems. - Alexandr Andoni; Aleksandar Nikolov; Krzysztof Onak; Grigory Yaroslavtsev (STOC, 2014)

The Sketching Complexity of Graph Cuts. - Alexandr Andoni; Robert Krauthgamer; David P. Woodruff (CoRR, 2014)

Practical and Optimal LSH for Angular Distance. - Alexandr Andoni; Piotr Indyk; Thijs Laarhoven; Ilya P. Razenshteyn; Ludwig Schmidt (NIPS, 2015)

Optimal Data-Dependent Hashing for Approximate Near Neighbors. - Alexandr Andoni; Ilya P. Razenshteyn (STOC, 2015)

High-Dimensional Computational Geometry. - Alexandr Andoni (Handbook of Big Data, 2016)

Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. - Alexandr Andoni; Ilya P. Razenshteyn (SoCG, 2016)

Interacting with Large Distributed Datasets Using Sketch. - Mihai Budiu; Rebecca Isaacs; Derek Murray; Gordon D. Plotkin; Paul Barham 001; Samer Al-Kiswany; Yazan Boshmaf; Qingzhou Luo; Alexandr Andoni (EGPGV@EuroVis, 2016)

Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. - Alexandr Andoni; Assaf Naor; Ofer Neiman (ICALP, 2016)

On Sketching Quadratic Forms. - Alexandr Andoni; Jiecao Chen; Robert Krauthgamer; Bo Qin; David P. Woodruff; Qin Zhang 001 (ITCS, 2016)

Lower Bounds on Time-Space Trade-Offs for Approximate Near Neighbors. - Alexandr Andoni; Thijs Laarhoven; Ilya P. Razenshteyn; Erik Waingarten (CoRR, 2016)

Approximate Near Neighbors for General Symmetric Norms. - Alexandr Andoni; Aleksandar Nikolov; Ilya P. Razenshteyn; Erik Waingarten (CoRR, 2016)

Width of Points in the Streaming Model. - Alexandr Andoni; Huy L. Nguyên (ACM Trans. Algorithms, 2016)

Correspondence retrieval. - Alexandr Andoni; Daniel J. Hsu; Kevin Shi; Xiaorui Sun (COLT, 2017)

High frequency moments via max-stability. - Alexandr Andoni (ICASSP, 2017)

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. - Alexandr Andoni; Thijs Laarhoven; Ilya P. Razenshteyn; Erik Waingarten (SODA, 2017)

LSH Forest: Practical Algorithms Made Theoretical. - Alexandr Andoni; Ilya P. Razenshteyn; Negev Shekel Nosatzki (SODA, 2017)

Approximate near neighbors for general symmetric norms. - Alexandr Andoni; Huy L. Nguyen; Aleksandar Nikolov; Ilya P. Razenshteyn; Erik Waingarten (STOC, 2017)

Coding with asymmetric prior knowledge. - Alexandr Andoni; Javad Ghaderi; Daniel J. Hsu; Dan Rubenstein; Omri Weinstein (CoRR, 2017)

Editorial. - Alexandr Andoni; Debmalya Panigrahi; Marcin Pilipczuk (ACM Trans. Algorithms, 2017)

Hölder Homeomorphisms and Approximate Nearest Neighbors. - Alexandr Andoni; Assaf Naor; Aleksandar Nikolov; Ilya P. Razenshteyn; Erik Waingarten (FOCS, 2018)

Parallel Graph Connectivity in Log Diameter Rounds. - Alexandr Andoni; Zhao Song 002; Clifford Stein 001; Zhengyu Wang; Peilin Zhong (FOCS, 2018)

Subspace Embedding and Linear Regression with Orlicz Norm. - Alexandr Andoni; Chengyu Lin 001; Ying Sheng 004; Peilin Zhong; Ruiqi Zhong (ICML, 2018)

Data-dependent hashing via nonlinear spectral gaps. - Alexandr Andoni; Assaf Naor; Aleksandar Nikolov; Ilya P. Razenshteyn; Erik Waingarten (STOC, 2018)

Approximate Nearest Neighbor Search in High Dimensions. - Alexandr Andoni; Piotr Indyk; Ilya P. Razenshteyn (CoRR, 2018)

Batch Sparse Recovery, or How to Leverage the Average Sparsity. - Alexandr Andoni; Lior Kamma; Robert Krauthgamer; Eric Price 001 (CoRR, 2018)

Two Party Distribution Testing: Communication and Security. - Alexandr Andoni; Tal Malkin; Negev Shekel Nosatzki (IACR Cryptol. ePrint Arch., 2018)

Sketching and Embedding are Equivalent for Norms. - Alexandr Andoni; Robert Krauthgamer; Ilya P. Razenshteyn (SIAM J. Comput., 2018)

Attribute-efficient learning of monomials over highly-correlated variables. - Alexandr Andoni; Rishabh Dudeja; Daniel Hsu 001; Kiran Vodrahalli (ALT, 2019)

Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. - Alexandr Andoni; Clifford Stein 001; Peilin Zhong (ICALP, 2019)

On Solving Linear Systems in Sublinear Time. - Alexandr Andoni; Robert Krauthgamer; Yosef Pogrow (ITCS, 2019)

Streaming Complexity of SVMs. - Alexandr Andoni; Collin Burns; Yi Li 002; Sepideh Mahabadi; David P. Woodruff (APPROX-RANDOM, 2020)

Edit Distance in Near-Linear Time: it's a Constant Factor. - Alexandr Andoni; Negev Shekel Nosatzki (FOCS, 2020)

Parallel approximate undirected shortest paths via low hop emulators. - Alexandr Andoni; Clifford Stein 001; Peilin Zhong (STOC, 2020)

Approximate Nearest Neighbors Beyond Space Partitions. - Alexandr Andoni; Aleksandar Nikolov; Ilya P. Razenshteyn; Erik Waingarten (SODA, 2021)

From Average Embeddings To Nearest Neighbor Search. - Alexandr Andoni; David Cheikhi (CoRR, 2021)

Learning to Hash Robustly, with Guarantees. - Alexandr Andoni; Daniel Beaglehole (CoRR, 2021)

Special Section on the 48th Annual ACM Symposium on Theory of Computing (STOC 2016). - Alexandr Andoni; Keren Censor-Hillel; Jing Chen; Debmalya Panigrahi (SIAM J. Comput., 2021)

Estimating the Longest Increasing Subsequence in Nearly Optimal Time. - Alexandr Andoni; Negev Shekel Nosatzki; Sandip Sinha; Clifford Stein 001 (FOCS, 2022)

Learning to Hash Robustly, Guaranteed. - Alexandr Andoni; Daniel Beaglehole (ICML, 2022)

Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. - Alexandr Andoni; Hengjie Zhang (FOCS, 2023)

Data Structures for Density Estimation. - Anders Aamand; Alexandr Andoni; Justin Y. Chen; Piotr Indyk; Shyam Narayanan; Sandeep Silwal (ICML, 2023)

Communication Complexity of Inner Product in Symmetric Normed Spaces. - Alexandr Andoni; Jaroslaw Blasiok; Arnold Filtser (ITCS, 2023)

Differentially Private Approximate Near Neighbor Counting in High Dimensions. - Alexandr Andoni; Piotr Indyk; Sepideh Mahabadi; Shyam Narayanan (NeurIPS, 2023)

Massively Parallel Tree Embeddings for High Dimensional Spaces. - AmirMohsen Ahanchi; Alexandr Andoni; MohammadTaghi Hajiaghayi; Marina Knittel; Peilin Zhong (SPAA, 2023)

Sub-quadratic (1+ eps)-approximate Euclidean Spanners, with Applications. - Alexandr Andoni; Hengjie Zhang (CoRR, 2023)

Statistical-Computational Trade-offs for Density Estimation. - Anders Aamand; Alexandr Andoni; Justin Y. Chen; Piotr Indyk; Shyam Narayanan; Sandeep Silwal; Haike Xu (NeurIPS, 2024)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems. - Josh Alman; Alexandr Andoni; Hengjie Zhang (CoRR, 2024)

Faster Algorithms for Average-Case Orthogonal Vectors and Closes Pair Problems. - Josh Alman; Alexandr Andoni; Hengjie Zhang (SOSA, 2025)

A Framework for Building Data Structures from Communication Protocols. - Alexandr Andoni; Shunhua Jiang; Omri Weinstein (STOC, 2025)