Alexandr Andoni
Associate Professor, Columbia University
I am an associate professor at Columbia University, and member of the Data Science Institute. I have a broad interest in algorithmic foundations of massive data. Some particular interests include sublinear algorithms (streaming and property testing), high-dimensional computational geometry, metric embeddings, and machine learning.
I graduated from MIT in 2009, under the supervision of Prof. Piotr Indyk. My PhD thesis is "Nearest Neighbor Search: the Old, the New, and the Impossible".
In 2009-2010, I was a postdoc at the Center for Computational Intractability at Princeton, and a visitor at NYU and IAS. I was a researcher at Microsoft Research Silicon Valley lab, from 2010 until its closure in 2014. Afterwards, I was a visiting scientist at the Simons Institute for the Theory of Computing at UC Berkeley.
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).
- Edit Distance in Near-Linear Time: it's a Constant Factor (with Negev Shekel Nosatzki).
- Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators (with Clifford Stein, Peilin Zhong).
- Parallel Graph Connectivity in Log Diameter Rounds (with Zhao Song, Clifford Stein, Zhengyu Wang, Peilin Zhong).
- Data-dependent hashing via nonlinear spectral gaps (with Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, Erik Waingarten).
- Sketching and Embedding are Equivalent for Norms (with Robert Krauthgamer and Ilya Razenshteyn).
- Optimal Data-Dependent Hashing for Approximate Near Neighbors (with Ilya Razenshteyn).
- Parallel Algorithms for Geometric Graph Problems (with Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev).
- Streaming Algorithms via Precision Sampling (with Robert Krauthgamer and Krzysztof Onak).
- Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity (with Robert Krauthgamer and Krzysztof Onak).
- The Computational Hardness of Estimating Edit Distance (with Robert Krauthgamer).
- Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions (with Piotr Indyk).
Teaching (grad-level classes)
- 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).