Alexandr Andoni


420 S.W. Mudd

Alex Andoni investigates the algorithmic foundations of massive data. In particular, he is interested in discovering the fundamental design principles of algorithms for efficient processing of large datasets. 

Research Interests

Theoretical computer science, with a particular focus on sublinear algorithms (streaming and property testing), high-dimensional computational geometry, metric embeddings, theoretical machine learning, and the connections between these areas.

A prototypical problem is that of similarity search: given a set of objects such as images, find all pairs of similar objects quickly (faster than considering all possible pairs of objects, which is unaffordable for the sizes of modern datasets). This problem has numerous applications spanning many areas, including information retrieval, machine learning, data mining, computer vision, signal processing, and bioinformatics, and it underlies the classic "nearest neighbor" classification rule in machine learning.

Andoni develops new algorithmic design principles by leveraging advanced mathematical primitives for representing and manipulating data efficiently. For example, the above problem admits particularly fast algorithms if one can represent the objects using small “sketches” preserving relevant structure (the “similarity” in this case). The challenge then becomes to find the best sketch primitive. The general underlying theme is also to study models and algorithms with very restricted resources, such as space, time, measurements, samples, or communication. These questions are core questions in areas such as sublinear algorithms (namely, streaming algorithms, property testing, compressive sensing), high-dimensional geometry, metric embeddings, and others. Andoni has used and developed tools in these areas, collaborating with experts in theoretical computer science, mathematics, machine learning, and statistics, and ultimately providing novel approaches for many computational problems on massive datasets.

Andoni received a BS in computer science and engineering and a BS in mathematics in 2004, as well as a MS in electrical engineering and computer science in 2005 from Massachusetts Institute of Technology (MIT). He graduated with a PhD from MIT in 2009, with a thesis on Nearest Neighbor Search in high-dimensional spaces. Following graduation, he was a postdoctoral researcher at the Center for Computational Intractability, hosted by Princeton, NYU, and IAS. He then joined Microsoft Research Silicon Valley, where he was a full-time researcher until 2014. He was a visiting scientist at the Simons Institute for the Theory of Computing at UC Berkeley until joining Columbia in 2015.


  • Postdoctoral fellow, Center for Computational Intractability, Princeton, 2009—2010


  • Associate professor of computer science, Columbia University, 2015—
  • Visiting scientist, Simons Institute for the Theory of Computing, University of California Berkeley, 2014—2015
  • Researcher, Microsoft Research Silicon Valley, 2010—2014


  • Google Faculty Research Award


  • NSF, Google, Simons Foundation.


  • Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, Erik Waingarten. Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors. SODA (Symposium on Discrete Algorithms), 2017. Invited to T.Alg. special issue.
  • Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya Razenshteyn, and Ludwig Schmidt. Practical and Optimal LSH for Angular Distance. NIPS (Conference on Neural Information Processing Systems), 2015.
  • Alexandr Andoni, Robert Krauthgamer and Ilya Razenshteyn. Sketching and Embedding are Equivalent for Norms. STOC (Symposium on Theory of Computation), 2015. To appear in SIAM J. Comp. special issue.
  • Alexandr Andoni, Ilya Razenshteyn. Optimal Data-Dependent Hashing for Approximate Near Neighbors. STOC (Symposium on Theory of Computation), 2015.
  • Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, Grigory Yaroslavtsev. Parallel Algorithms for Geometric Graph Problems. STOC (Symposium on Theory of Computation), 2014.
  • Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak. Streaming Algorithms via Precision Sampling. FOCS (Symposium on Foundations of Computer Science), 2011.
  • Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak. Polylogarithmic Approximation to Edit Distance and Asymmetric Query Complexity. FOCS (Symposium on Foundations of Computer Science), 2010. Invited to SIAM J. Comp. special issue (declined).
  • Alexandr Andoni, Robert Krauthgamer. The Computational Hardness of Estimating Edit Distance. FOCS (Symposium on Foundations of Computer Science), 2007. Also in SIAM J. Comp. special issue.
  • Alexandr Andoni, Piotr Indyk, Mihai Patrascu. On Optimality of the Dimensionality Reduction Method. FOCS (Symposium on Foundations of Computer Science), 2006.
  • Alexandr Andoni, Piotr Indyk. Near-optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. CACM (Communications of the ACM), 51(1):117–122, 2008.