Alexandr Andoni

Book Chapters / Surveys:

• Approximate Nearest Neighbor Search in High Dimensions (with Piotr Indyk and Ilya Razenshteyn).
  In the proceedings of ICM'18 (accompanying the talk by P. Indyk). 2018.
  
  
• "High-dimensional computational geometry". Book chapter in Handbook on Big Data, Peter Buhlmann, Petros Drineas, Michael Kane, Mark van der Laan (eds.), CRC Press, 2016.
  
  
• Nearest neighbors in high-dimensional spaces (with Piotr Indyk). Book chapter in Handbook of Discrete and Computational Geometry (3rd edition), Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Toth (eds), CRC Press LLC, 2016.
  
  
• "Locality-sensitive hashing using stable distributions" (with Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab Mirrokni), in "Nearest Neighbor Methods in Learning and Vision: Theory and Practice", T. Darrell and P. Indyk and G. Shakhnarovich (eds.), MIT Press, 2006. See also the Intro to that book.
  
  

Publications:

• Fixed Universal Transformers (with Jingwen Liu, Daniel Hsu). Preprint/in submission. Also in Mechanistic Interpretability Workshop (ICML'26).
  
  
• Nearly Optimal Attention Coresets (with Edo Liberty, Eldar Kleiner). Preprint.
  
  
• Approximate Orthogonal Vectors and Diameter via Regularity Lemma (with Shunhua Jiang, Styopa Zharkov).
  In STOC'26.
  
  
• Fast attention mechanisms: a tale of parallelism (with Jingwen Liu, Hantao Yu, Clayton Sanford, Daniel Hsu).
  In NeurIPS'25.
  
  
• Embeddings into Similarity Measures for Nearest Neighbor Search (with Negev Shekel Nosatzki).
  In FOCS'25.
  
  
• A Framework for Building Data Structures from Communication Protocols (with Shunhua Jiang, Omri Weinstein).
  In STOC'25.
  
  
• Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems (with Josh Alman, Hengjie Zhang).
  In SOSA'25.
  
  
• Statistical-Computational Trade-offs for Density Estimation (with Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal, Haike Xu ).
  In NeurIPS'24.
  
  
• Differentially Private Approximate Near Neighbor Counting in High Dimensions (with Piotr Indyk, Sepideh Mahabadi, Shyam Narayanan).
  In NeurIPS'23.
  
  
• Sub-quadratic (1+epsilon)-approximate Euclidean Spanners, with Applications (with Hengjie Zhang).
  In FOCS'23.
  
  
• Data Structures for Density Estimation (with Anders Aamand, Justin Y. Chen, Piotr Indyk, Shyam Narayanan, Sandeep Silwal ).
  In ICML'23.
  
  
• Massively Parallel Tree Embeddings for High Dimensional Spaces (with AmirMohsen Ahanchi, MohammadTaghi Hajiaghayi, Marina Knittel, Peilin Zhong).
  In SPAA'23.
  
  
• Communication Complexity of Inner Product in Symmetric Normed Spaces (with Arnold Filtser, Jarosław Błasiok).
  In ITCS'23.
  
  
• Estimating the Longest Increasing Subsequence in Nearly Optimal Time (with Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein).
  In FOCS'22.
  
  
• Learning to Hash Robustly, Guaranteed (with Daniel Beaglehole).
  In ICML'22.
  
  
• Approximate Nearest Neighbors Beyond Space Partitions (with Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten).
  In SODA'21.
  
  
• Edit Distance in Near-Linear Time: it's a Constant Factor (with Negev Shekel Nosatzki).
  In FOCS'20.
  
  
• Streaming Complexity of SVMs (with Collin Burns, Yi Li, Sepideh Mahabadi, David P. Woodruff).
  In APPROX'20.
  
  
• Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators (with Clifford Stein, Peilin Zhong).
  In STOC'20.
  
  
• Two Party Distribution Testing: Communication and Security (with Tal Malkin and Negev Shekel Nosatzki).
  In ICALP'19. Full version at ePrint 2018/1086 and arXiv:1811.04065.
  
  
• Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity (with Cliff Stein and Peilin Zhong).
  In ICALP'19.
  
  
• Attribute-efficient learning of monomials over highly-correlated variables (with Rishabh Dudeja, Daniel Hsu, Kiran Vodrahalli).
  In ALT'19.
  
  
• On Solving Linear Systems in Sublinear Time (with Robert Krauthgamer and Yosef Pogrow).
  In ITCS'19.
  
  
• Simpler Constant-Factor Approximation to Edit Distance Problems
  Manuscript 2018. A bare-bones (simplest version) 3+eps approximation algorithm is also distilled here.
  
  
• Holder Homeomorphisms and Approximate Nearest Neighbors (with Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten).
  In FOCS'18.
  
  
• Parallel Graph Connectivity in Log Diameter Rounds (with Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong).
  In FOCS'18.
  
  
• Subspace Embedding and Linear Regression with Orlicz Norm (with Chengyu Lin, Ying Sheng, Peilin Zhong, Ruiqi Zhong).
  In ICML'18.
  
  
• Data-dependent hashing via nonlinear spectral gaps (with Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten).
  In STOC'18.
  
  
• Coding with asymmetric prior knowledge (with Javad Ghaderi, Daniel Hsu, Dan Rubenstein, and Omri Weinstein).
  arXiv:1707.04875
  
  
• Correspondence retrieval (with Daniel Hsu, Kevin Shi, and Xiaorui Sun).
  In COLT'17.
  
  
• Approximate Near Neighbors for General Symmetric Norms (with Huy L. Nguyen, Sasho Nikolov, Ilya Razenshteyn, and Erik Waingarten).
  In STOC'17. arXiv:1611.06222
  
  
• High frequency moments via max-stability.
  In ICASSP, special session on Random Embeddings and Geometry-Preserving Dimensionality Reduction, 2017.
  
  
• Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors (with Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten).
  In SODA'17. Invited to T.Alg. special issue. arXiv:1608.03580.
  
  
• LSH Forest: Practical Algorithms Made Theoretical (with Ilya Razenshteyn and Negev Shekel-Nosatzki).
  In SODA'17.
  
  
• Snowflake universality of Wasserstein spaces (with Assaf Naor and Ofer Neiman).
  In Annales scientifiques de l'ENS (Eng. Scientific Annals of ENS). arXiv:1509.08677. A CS version appears in ICALP'16 (see below).
  
  
• Impossibility of Sketching of the 3D Transportation Metric with Quadratic Cost (with Assaf Naor and Ofer Neiman).
  In ICALP'16. This a CS version of the above journal paper (arXiv:1509.08677).
  
  
• Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing (with Ilya Razenshteyn).
  In SoCG'16. arXiv:1507.04299.
  
  
• On Sketching Quadratic Forms (with Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, Qin Zhang).
  In ITCS'16. Also in arXiv:1511.06099, and subsumes the earlier arXiv:1403.7058.
  
  
• Practical and Optimal LSH for Angular Distance (with Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn and Ludwig Schmidt).
  In NIPS'15. arXiv:1509.02897.
  
  
• Sketching and Embedding are Equivalent for Norms (with Robert Krauthgamer and Ilya Razenshteyn).
  In STOC'15, and SICOMP special issue. Also arXiv:1411.2577.
  
  
• Optimal Data-Dependent Hashing for Approximate Near Neighbors (with Ilya Razenshteyn).
  In STOC'15. arXiv:1501.01062.
  
  
• Spectral Approaches to Nearest Neighbor Search (with Amirali Abdullah, Ravi Kannan, and Robert Krauthgamer).
  In FOCS'14. arXiv:1408.0751. versions: arXiv:1408.0751, conference version.
  
  
• Learning Polynomials with Neural Networks (with Rina Panigrahy, Gregory Valiant, and Li Zhang).
  In ICML'14. The draft of a full version is available here.
  
  
• Parallel Algorithms for Geometric Graph Problems (with Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev).
  In STOC'14. versions: arXiv 1401.0042, local copy.
  
  
• Beyond Locality Sensitive Hashing (with Piotr Indyk, Huy L. Nguyen, and Ilya Razenshteyn).
  In SODA'14. versions: local copy, arXiv:1306.1547
  
  
• Towards (1+epsilon)-Approximate Flow Sparsifiers (with Robert Krauthgamer and Anupam Gupta).
  In SODA'14. versions: conference version, arXiv 1310.3252
  
  
• Learning Sparse Polynomial Functions (with Rina Panigrahy, Gregory Valiant, and Li Zhang).
  In SODA'14.
  
  
• "Tight Lower Bound for Linear Sketches of Moments" (joint with Huy L. Nguyen, Yury Polyanskiy, and Yihong Wu).
  In ICALP, 2013. See also arXiv version.
  
  
• "Homomorphic Fingerprints under Misalignments: Sketching Edit and Shift Distances" (joint with Assaf Goldberger, Andrew McGregor, and Ely Porat).
  In STOC'13.
  
  
• "Shift Finding in Sub-linear Time" (joint with Haitham Hassanieh, Piotr Indyk, and Dina Katabi). In SODA'13.
  
  
• "Eigenvalues of a Matrix in the Streaming Model" (joint with Huy L. Nguyen). In SODA'13.
  
  
• "Width of Points in the Streaming Model" (with Huy L. Nguyen). Accepted to Transactions on Algorithms special issue of SODA'12. Previously in SODA'12.
  download: journal version.
  
  
• "Near Linear Lower Bound for Dimension Reduction in L1" (with Moses Charikar, Ofer Neiman, and Huy L. Nguyen). In FOCS'11.
  download: conference version.
  
  
• "Streaming Algorithms via Precision Sampling" (with Robert Krauthgamer and Krzysztof Onak). In FOCS'11. Full version on arXiv:1011.1263.
  download: arXiv version, conference version.
  
  
• "Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity" (with Robert Krauthgamer and Krzysztof Onak). In Proceedings of Symposium on Foundations of Computer Science (FOCS'10), 2010. Invited to SICOMP special issue (declined).
  download: arXiv version, conference version.
  
  
• "Global Alignment of Molecular Sequences via Ancestral State Reconstruction" (with Constantinos Daskalakis, Avinatan Hassidim, and Sebastien Roch). Stochastic Processes and their Applications 122 (2012), pp. 3852--3874. Extended abstract in Proceedings of the Symposium on Innovations in Computer Science (ICS'10), 2010.
  download: [journal version]
  
  
• "Lower bounds for Edit Distance and Product Metrics via Poincare-Type Inequalities" (with T.S. Jayram and Mihai Pătraşcu). In Proceedings of the Symposium on Discrete Algorithms (SODA'10), 2010.
  download: [.pdf, .ps].
  
  
• "Near-Optimal Sublinear Time Algorithms for Ulam Distance" (with Huy L. Nguyen). In Proceedings of the Symposium on Discrete Algorithms (SODA'10), 2010.
  download: [.pdf, .ps].
  
  
• "Efficient sketches for Earth-Mover Distance, with applications" (with Khanh Do Ba, Piotr Indyk, and David Woodruff). In Proceedings of Symposium on Foundations of Computer Science (FOCS'09), 2009.
  download: [.pdf, .ps].
  
  
• "External Sampling" (with Piotr Indyk, Krzysztof Onak, and Ronitt Rubinfeld). In Proceedings of International Colloquium on Automata, Languages and Programming (ICALP'09), 2009.
  download: [.pdf, .ps].
  
  
• "Approximating Edit Distance in Near-Linear Time" (with Krzysztof Onak). In Proceedings of the Symposium on Theory of Computing (STOC'09), 2009. SIAM J. Comp. (SICOMP), special issue of STOC'09. Previously in STOC'09, arXiv:1109.5635.
  download: journal version [.pdf, .ps], arXiv version.
  
  
• "Approximate Line Nearest Neighbor in High Dimensions" (with Piotr Indyk, Robert Krauthgamer, and Huy L. Nguyen). In Proceedings of the Symposium on Discrete Algorithms (SODA'09), 2009.
  download: [.pdf, .ps].
  
  
• "Overcoming the L1 Non-Embeddability Barrier: Algorithms for Product Metrics" (with Piotr Indyk and Robert Krauthgamer). In Proceedings of the Symposium on Discrete Algorithms (SODA'09), 2009.
  download: [.pdf, .ps]. For temporary "full version", see Chapter 5 in the PhD thesis.
  
  
• "Hardness of Nearest Neighbor under L-infinity" (with Dorian Croitoru and Mihai Pătraşcu). In Proceedings of Symposium on Foundations of Computer Science (FOCS'08), 2008.
  download: [.pdf, .ps].
  
  
• "The Smoothed Complexity of Edit Distance" (with Robert Krauthgamer). In TALG. Previously in Proceedings of International Colloquium on Automata, Languages and Programming (ICALP'08), 2008.
  download: [journal version, conference version].
  
  
• "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions" (with Piotr Indyk). Communications of the ACM, vol. 51, no. 1, 2008, pp. 117-122.
  download: local .ps copy, or directly from CACM (for free). CACM disclaimer.
  
  
• "Earth Mover Distance over High-Dimensional Spaces" (with Piotr Indyk and Robert Krauthgamer). In Proceedings of the Symposium on Discrete Algorithms(SODA'08), 2008. Previously ECCC TR07-048.
  download: [.pdf, .ps]
  
  
• "The Computational Hardness of Estimating Edit Distance" (with Robert Krauthgamer). SIAM J. on Computing (FOCS'07 special issue), vol.39, no.6, 2010. Extended abstract in Proceedings of Symposium on Foundations of Computer Science (FOCS'07), 2007.
  download: journal version [.pdf, .ps]
  
  
• "Testing k-wise and Almost k-wise independence" (with Noga Alon, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning Xie). In Proceedings of ACM Symposium on Theory of Computing (STOC'07), 2007. Full version in preparation.
  download: [.pdf, .ps]
  
  
• "Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions" (with Piotr Indyk). In Proceedings of the Symposium on Foundations of Computer Science (FOCS'06), 2006.
  download: [.pdf, .ps]. For current "full version", see Chapter 3 in the PhD thesis.
  
  
• "On the Optimality of the Dimensionality Reduction Method" (with Mihai Pătraşcu and Piotr Indyk). In Proceedings of the Symposium on Foundations of Computer Science (FOCS'06), 2006.
  download: [.pdf, .ps]
  
  
• "Efficient Algorithms for Substring Near Neighbor Problem" (with Piotr Indyk). In Proceedings of the Symposium on Discrete Algorithms (SODA'06), 2006. For a full version, see my Master's thesis below.
  download: [.pdf, .ps, .ppt talk]
  
  
• "Graceful Service Degradation (or, How to Know Your Payment Is Late)" (with Jessica Staddon). Proceedings of the 6th ACM Conference on Electronic Commerce (EC'05) , Vancouver, June 2005.
  download: [.pdf, .ps, .ppt talk]
  
  
• "An evaluation of exhaustive testing for data structures" (with Darko Marinov, Dumitru Daniliuc, Sarfraz Khurshid, and Martin Rinard). Technical Report MIT-LCS-TR-921, MIT CSAIL, Cambridge, MA, September 2003.
  download: [.pdf, .ps]
  
  
• "Lower Bounds for Embedding of Edit Distance into Normed Spaces" (with Michel Deza, Anupam Gupta, Piotr Indyk, and Sofya Raskhodnikova). Proceedings of the 14th Symposium on Discrete Algorithms (SODA'03) , 2003.
  download: [.pdf, .ps, .ppt talk]

Manuscripts:

• "Simpler Constant-Factor Approximation to Edit Distance Problems ". Manuscript, 2018.
  
  
• "Phylogenetic Reconstruction with Insertions and Deletions" (with Mark Braverman and Avinatan Hassidim). Manuscript, 2010.
  
  
• "Distance Estimation Protocols for General Metrics" (with Robert Krauthgamer). Manuscript, 2008.
  
  
• Dimension Reduction in Kernel Spaces from Locality-Sensitive Hashing" (with Piotr Indyk). Manuscript, 2008. See also Chapter 4 of my PhD Thesis.
  
  
• "Block Heavy Hitters" (with Khanh Do Ba and Piotr Indyk). MIT Technical Report MIT-CSAIL-TR-2008-024, 2008.
  download: available here.
  
  

Theses: