| 2026 | STOC | Approximate Orthogonal Vectors and Diameter via Regularity Lemma. | Alexandr Andoni, Shunhua Jiang, Stepan Zharkov |
| 2025 | FOCS | Embeddings into Similarity Measures for Nearest Neighbor Search. | Alexandr Andoni, Negev Shekel Nosatzki |
| 2025 | STOC | A Framework for Building Data Structures from Communication Protocols. | Alexandr Andoni, Shunhua Jiang, Omri Weinstein |
| 2023 | FOCS | Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications. | Alexandr Andoni, Hengjie Zhang |
| 2023 | ICML | Data Structures for Density Estimation. | Anders Aamand, Alexandr Andoni, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal |
| 2023 | SPAA | Massively Parallel Tree Embeddings for High Dimensional Spaces. | AmirMohsen Ahanchi, Alexandr Andoni, MohammadTaghi Hajiaghayi, Marina Knittel, Peilin Zhong |
| 2022 | FOCS | Estimating the Longest Increasing Subsequence in Nearly Optimal Time. | Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein |
| 2022 | ICML | Learning to Hash Robustly, Guaranteed. | Alexandr Andoni, Daniel Beaglehole |
| 2021 | SODA | Approximate Nearest Neighbors Beyond Space Partitions. | Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2020 | FOCS | Edit Distance in Near-Linear Time: it's a Constant Factor. | Alexandr Andoni, Negev Shekel Nosatzki |
| 2020 | STOC | Parallel approximate undirected shortest paths via low hop emulators. | Alexandr Andoni, Clifford Stein, Peilin Zhong |
| 2019 | ALT | Attribute-efficient learning of monomials over highly-correlated variables. | Alexandr Andoni, Rishabh Dudeja, Daniel Hsu, Kiran Vodrahalli |
| 2019 | ICALP | Two Party Distribution Testing: Communication and Security. | Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki |
| 2019 | ICALP | Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity. | Alexandr Andoni, Clifford Stein, Peilin Zhong |
| 2018 | FOCS | Hlder Homeomorphisms and Approximate Nearest Neighbors. | Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2018 | FOCS | Parallel Graph Connectivity in Log Diameter Rounds. | Alexandr Andoni, Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong |
| 2018 | ICML | Subspace Embedding and Linear Regression with Orlicz Norm. | Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong |
| 2018 | STOC | Data-dependent hashing via nonlinear spectral gaps. | Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2017 | COLT | Correspondence retrieval. | Alexandr Andoni, Daniel J. Hsu, Kevin Shi, Xiaorui Sun |
| 2017 | ICASSP | High frequency moments via max-stability. | Alexandr Andoni |
| 2017 | SODA | Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. | Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, Erik Waingarten |
| 2017 | SODA | LSH Forest: Practical Algorithms Made Theoretical. | Alexandr Andoni, Ilya P. Razenshteyn, Negev Shekel Nosatzki |
| 2017 | STOC | Approximate near neighbors for general symmetric norms. | Alexandr Andoni, Huy L. Nguyen, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten |
| 2016 | EGPGV | Interacting with Large Distributed Datasets Using Sketch. | Mihai Budiu, Rebecca Isaacs, Derek Murray, Gordon D. Plotkin, Paul Barham, Samer Al-Kiswany, Yazan Boshmaf, Qingzhou Luo, Alexandr Andoni |
| 2016 | ICALP | Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost. | Alexandr Andoni, Assaf Naor, Ofer Neiman |
| 2015 | STOC | Sketching and Embedding are Equivalent for Norms. | Alexandr Andoni, Robert Krauthgamer, Ilya P. Razenshteyn |
| 2015 | STOC | Optimal Data-Dependent Hashing for Approximate Near Neighbors. | Alexandr Andoni, Ilya P. Razenshteyn |
| 2014 | FOCS | Spectral Approaches to Nearest Neighbor Search. | Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer |
| 2014 | ICML | Learning Polynomials with Neural Networks. | Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang |
| 2014 | SODA | Towards (1 + | Alexandr Andoni, Anupam Gupta, Robert Krauthgamer |
| 2014 | SODA | Beyond Locality-Sensitive Hashing. | Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, Ilya P. Razenshteyn |
| 2014 | SODA | Learning Sparse Polynomial Functions. | Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang |
| 2014 | STOC | Parallel algorithms for geometric graph problems. | Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev |
| 2013 | ICALP | Tight Lower Bound for Linear Sketches of Moments. | Alexandr Andoni, Huy L. Nguyn, Yury Polyanskiy, Yihong Wu |
| 2013 | SODA | Shift Finding in Sub-Linear Time. | Alexandr Andoni, Piotr Indyk, Dina Katabi, Haitham Hassanieh |
| 2013 | SODA | Eigenvalues of a matrix in the streaming model. | Alexandr Andoni, Huy L. Nguyen |
| 2013 | STOC | Homomorphic fingerprints under misalignments: sketching edit and shift distances. | Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat |
| 2012 | SODA | Width of points in the streaming model. | Alexandr Andoni, Huy L. Nguyen |
| 2011 | FOCS | Near Linear Lower Bound for Dimension Reduction in L1. | Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen |
| 2011 | FOCS | Streaming Algorithms via Precision Sampling. | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2011 | MFCS | Nearest Neighbor Search in High-Dimensional Spaces. | Alexandr Andoni |
| 2010 | FOCS | Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2010 | SODA | Lower Bounds for Edit Distance and Product Metrics via Poincar-Type Inequalities. | Alexandr Andoni, T. S. Jayram, Mihai Patrascu |
| 2010 | SODA | Near-Optimal Sublinear Time Algorithms for Ulam Distance. | Alexandr Andoni, Huy L. Nguyen |
| 2009 | FOCS | Efficient Sketches for Earth-Mover Distance, with Applications. | Alexandr Andoni, Khanh Do Ba, Piotr Indyk, David P. Woodruff |
| 2009 | ICALP | External Sampling. | Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld |
| 2009 | SODA | Overcoming the | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer |
| 2009 | SODA | Approximate line nearest neighbor in high dimensions. | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer, Huy L. Nguyen |
| 2009 | STOC | Approximating edit distance in near-linear time. | Alexandr Andoni, Krzysztof Onak |
| 2008 | FOCS | Hardness of Nearest Neighbor under L-infinity. | Alexandr Andoni, Dorian Croitoru, Mihai Patrascu |
| 2008 | ICALP | The Smoothed Complexity of Edit Distance. | Alexandr Andoni, Robert Krauthgamer |
| 2008 | SIGMOD | 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, Mihai Patrascu, D. Sivakumar |
| 2008 | SODA | Earth mover distance over high-dimensional spaces. | Alexandr Andoni, Piotr Indyk, Robert Krauthgamer |
| 2007 | FOCS | The Computational Hardness of Estimating Edit Distance [Extended Abstract]. | Alexandr Andoni, Robert Krauthgamer |
| 2007 | STOC | Testing k-wise and almost k-wise independence. | Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie |
| 2006 | FOCS | Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. | Alexandr Andoni, Piotr Indyk |
| 2006 | FOCS | On the Optimality of the Dimensionality Reduction Method. | Alexandr Andoni, Piotr Indyk, Mihai Patrascu |
| 2006 | SODA | Efficient algorithms for substring near neighbor problem. | Alexandr Andoni, Piotr Indyk |
| 2003 | SODA | Lower bounds for embedding edit distance into normed spaces. | Alexandr Andoni, Michel Deza, Anupam Gupta, Piotr Indyk, Sofya Raskhodnikova |