Alexandr Andoni
Associate Professor, Columbia University
I am an associate professor of Computer Science, member of Columbia Core AI Lab, and Foundations of Data Science. I'm broadly interested in algorithmic foundations of large-scale, high-dimensional 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.
Teaching (selected)
- Algorithms in Large Language Models, COMS 6998 (Fall'26).
- Algorithms for Massive Data, COMS 6998 (Fall'25).
- Advanced Algorithms, COMS 4232 (Spring'21).
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. [This is outdated now -- if you are interested in fast solutions to NNS, check out, e.g., ANN Benchmarks.]
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.