Alexandr Andoni
Info about me:
If you are a prospective graduate student and are interested to work
with me, please consider to apply to
our PhD program here. I am looking to hire great PhD students.
I am an associate professor at
Columbia
University.
I have 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.
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.
Afterwards, I was a visiting scientist at the Simons Institute for the Theory of Computing at UC Berkeley.
Publications
CV
Teaching:
Algorithmic
Techniques for Massive Data, COMS 69989 (Fall'15).
Analysis
of Algorithms I, CSOR W42312 (Fall'16). (Registered Columbia
students can access the full website via Courseworks.)
Former interns:
I've had the pleasure to supervise the following students while at MSRSVC:
Lectures and talks:

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
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: STOC'16, MASSIVE'15, RANDOM'15, SODA'15, FOCS'13, MASSIVE'12, APPROX'12,
ESAB'12 (experimental track), STOC'11, CPM'11, RANDOM'10.

Coorganizer of the workshop
on Big Data
through the Lens of Sublinear Algorithms at DIMACS, Rutgers
University (together with Muthu Muthukrishnan and Grigory Yaroslavtsev).

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:
Office: Mudd 420. Office hours: Wed 45pm.
Email: