Alexandr Andoni

Info about me:

I am a reseacher in Theoretical Computer Science. My research interests broadly revolve around big data algorithmics, sublinear algorithms, and theoretical machine learning. Some technical interests include high-dimensional computational geometry, metric embeddings, streaming, property testing, learning.

I graduated from MIT in 2009, under the supervision of Prof. Piotr Indyk. My PhD thesis is on the "Nearest Neighbor Search: the Old, the New, and the Impossible" [.pdf, .ps]. 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 September 2014.

Former interns:
Lectures and talks:

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).

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.

Professional Service:

Program Committee of: SODA'15, FOCS'13, MASSIVE'12, APPROX'12, ESA-B'12 (experimental track), STOC'11, CPM'11, RANDOM'10.
Co-organizer of the Bertinoro Workshop on Sublinear Algorithms 2014 (together with Piotr Indyk, Robert Krauthgamer, and Sofya Raskhodnikova).
Co-organizer of the "Data Structures (in memory of Mihai Pătraşcu)" workshop at FOCS'12 (together with Erik Demaine, Piotr Indyk, and Mikkel Thorup).
Co-organizer of the workshop on embeddings as part of the Discrete Analysis programme at the Isaac Newton Institute for Mathematical Sciences, Cambridge, UK (together with Tim Austin and Assaf Naor).


CV (outdated)


I maintain a page on Locality-Sensitive Hashing (LSH). LSH is a practical algorithm for approximate nearest neighbor problem (in high dimensions).

Other (i.e., random stuff):

ACM ICPC: I used to be one of the coaches for the MIT's team for ACM International Collegiate Programming Contest.

AntiChess: Play my AntiChess :) (a 6.170 class project, joint with Cristian Cadar and Tudor Leu). Warning: the rendering might be suboptimal (different browsers tend to diplay the board sligthly differently). If you find 3min too little, you can change the time in the menus ('Options->Change player options').

A paranthesis 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 :).

Contact Info: