Alexandr Andoni
Info about me:
I am a computer scientist, with a broad interest in
algorithmic foundations of massive data.
Some particular interests include sublinear algorithms (streaming and
property testing), highdimensional computational geometry, metric
embeddings, and machine learning.
Currently, I am a visiting scientist at the Simons
Institute for the Theory of Computing at UC Berkeley.
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 20092010, 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.
Publications
CV (short bio)
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).

MADALGO Center for Massive Data
Algorithmics and CTIC Summer School on
HighDimensional Geometric Computing
lectures: Lecture
1, Lecture 2, Lecture 3.

Talk on "Nearest Neighbor Search in
HighDimensional 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: RANDOM'15, SODA'15, FOCS'13, MASSIVE'12, APPROX'12,
ESAB'12 (experimental track), STOC'11, CPM'11, RANDOM'10.

Coorganizer
of the Bertinoro
Workshop on Sublinear Algorithms 2014 (together with Piotr
Indyk, Robert Krauthgamer, and Sofya Raskhodnikova).

Coorganizer
of the "Data Structures (in memory of Mihai Pătraşcu)"
workshop at FOCS'12
(together with Erik Demaine, Piotr Indyk, and Mikkel
Thorup).

Coorganizer
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).
LSH:
I maintain a page on LocalitySensitive
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 hardtoexplain bureaucracy), Alexander
Andoni ("anglified" version), and Alex Andoni (simplified version :).
Contact Info:
Email: