Alexandr Andoni

Associate Professor, Columbia University

I am an associate professor of Computer Science, member of Columbia Core AI Lab, member of the Data Science Institute. I'm broadly interested in algorithmic foundations of large-scale data, especially with applications to more efficient machine learning.

Previously, I spent significant amount of time at MIT, Center for Computational Intractability at Princeton, NYU and IAS, Simons Institute for the Theory of Computing at UC Berkeley, as well as at Microsoft Research Silicon Valley lab.

If you are a prospective graduate student and are interested to work with me, please consider applying to our PhD program here. I am always looking to hire great PhD students.

Selected publications (all publications)

A Framework for Building Data Structures from Communication Protocols (with Shunhua Jiang, Omri Weinstein). In STOC'25.
Edit Distance in Near-Linear Time: it's a Constant Factor (with Negev Shekel Nosatzki). In FOCS'20.
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators (with Clifford Stein, Peilin Zhong). In STOC'20.
Parallel Graph Connectivity in Log Diameter Rounds (with Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong). In FOCS'18.
Data-dependent hashing via nonlinear spectral gaps (with Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten). In STOC'18.
Sketching and Embedding are Equivalent for Norms (with Robert Krauthgamer and Ilya Razenshteyn). In STOC'15, and SICOMP special issue 2018.
Optimal Data-Dependent Hashing for Approximate Near Neighbors (with Ilya Razenshteyn). In STOC'15.
Parallel Algorithms for Geometric Graph Problems (with Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev). In STOC'14.
Streaming Algorithms via Precision Sampling (with Robert Krauthgamer and Krzysztof Onak). In FOCS'11.
Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity (with Robert Krauthgamer and Krzysztof Onak). In FOCS'10. Invited to SICOMP special issue (regretfully declined).
The Computational Hardness of Estimating Edit Distance (with Robert Krauthgamer). In FOCS'07, and SICOMP special issue 2010.
Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions (with Piotr Indyk). Communications of the ACM, 2008.

Teaching (grad-level classes)

Algorithms for Large Language Models, COMS 6998 (Fall'26).
Algorithms for Massive Data, COMS 6998 (Fall'25).
Algorithms for Massive Data, COMS 6998-15 (Fall'23).
Advanced Algorithms, COMS 4232 (Spring'21).
Advanced Algorithms, COMS 4995-2 (Spring'20).
Algorithms for Massive Data, COMS 6998-9 (Spring'19).
Algorithms through Geometric Lens (Fall'17).
Advanced Algorithms, COMS 4995-3 (Spring'17).
Algorithmic Techniques for Massive Data, COMS 6998-9 (Fall'15).

Advising

I have the pleasure to advise a number of brilliant researchers, including:

Students

Former students, postdocs, and interns

Negev Shekel Nosatzki
Shunhua Jiang
Hengjie Zhang
Jaroslaw Blasiok (Simons Junior Fellow 2019)
Sandip Sinha
Kiran Vodrahalli
Arnold Filtser (member of the Simons Collaboration on Algorithms and Geometry)
Peilin Zhong
Ben Cousins (member of the Simons Collaboration on Algorithms and Geometry)
Sepideh Mahabadi (member of the Simons Collaboration on Algorithms and Geometry)
Ilya Razenshteyn (Simons Junior Fellow 2017, and MSR-SVC Intern 2014)
Amirali Abdullah (MSR-SVC Intern 2013)
Grigory Yaroslavtsev (MSR-SVC Intern 2012)
Huy Nguyen (MSR-SVC Intern 2011)

LSH

I maintain a page on Locality-Sensitive Hashing (LSH), which is an algorithm for approximate nearest neighbor problem (in high dimensions). Check out the related FALCONN software package as well.

Lectures and talks

Public lecture on Geometry of Similarity Search [as pdf] at the Simons Foundation.
Talk on Data-dependent Hashing for Similarity Search at the International Conference on Similarity Search and Applications (SISAP'16).
MADALGO Center for Massive Data Algorithmics Summer School on Streaming Algorithms: Lecture 1, Lecture 2, Lecture 3.
Graph Theory, Algorithms and Applications 3rd edition (summer school at the International School of Mathematics "Guido Stampacchia"): Sampling in Graphs: cut sparsifiers, Sampling in Graphs: node sparsifiers.
Summer School on Hashing: Theory and Practice (2014, University of Copenhagen): Dimension Reductions, Locality Sensitive Hashing.
Big Data Boot Camp (@ Simons Institute for Theory of Computing), Lectures on "Algorithmic High Dimensional Geometry": Lecture 1, Lecture 2, and references from the lectures.
School on ALgorithms for MAssive DAta (ALMADA'13) lectures: Lecture 1 (NNS), Lecture 2 (dimension reduction and NNS), Lecture 3 (streaming), Lecture 4 (parallel algorithms).
MADALGO Center for Massive Data Algorithmics and CTIC Summer School on High-Dimensional Geometric Computing lectures: Lecture 1, Lecture 2, Lecture 3.
Talk on "Nearest Neighbor Search in High-Dimensional Spaces" at the 36th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2011, and older version (pdf format) at the Workshop on Barriers in Computational Complexity II, 2010.

Other

A parenthesis that will hopefully help search engines better index my webpage. Alternative spellings of my name are: Alexandru Andoni (in Romanian, my normal name, although not the official one due to some hard-to-explain bureaucracy), Alexander Andoni ("anglified" version), and Alex Andoni (simplified version).