 Publications
 Teaching
 cv
 Office: Mudd 420.
 Email:
 Phone: 2128530685
 Mailing address:
Department of Computer Science
Columbia University
450 Computer Science Building
1214 Amsterdam Avenue, Mail Code 0401
New York, NY 10027
Alexandr Andoni
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), 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".
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.
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.
LSH:
I maintain
a page on LocalitySensitive
Hashing (LSH), which is an algorithm for approximate nearest
neighbor problem (in high dimensions). Check out the related
FALCONN
software package as well.

Edit Distance in NearLinear Time: it's a Constant Factor
(with Negev Shekel Nosatzki).
In FOCS'20.

Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
(with Clifford Stein, Peilin Zhong).
In STOC'20.

Parallel Graph Connectivity in Log Diameter Rounds (with Zhao
Song, Clifford Stein, Zhengyu Wang, Peilin Zhong).
In FOCS'18.

Datadependent hashing via nonlinear
spectral gaps (with Assaf Naor, Aleksandar Nikolov, Ilya
P. Razenshteyn, Erik Waingarten).
In STOC'18.

Sketching and Embedding are Equivalent for Norms (with Robert
Krauthgamer and Ilya Razenshteyn).
In STOC'15, and SICOMP special issue 2018.

Optimal DataDependent Hashing for
Approximate Near Neighbors (with Ilya Razenshteyn).
In STOC'15.

Parallel Algorithms for Geometric Graph
Problems (with Aleksandar Nikolov, Krzysztof Onak, and Grigory
Yaroslavtsev).
In STOC'14.

Streaming Algorithms via Precision Sampling (with Robert Krauthgamer
and Krzysztof Onak).
In FOCS'11.

Polylogarithmic
Approximation for Edit Distance and the Asymmetric Query Complexity
(with Robert Krauthgamer and Krzysztof
Onak).
In FOCS'10. Invited to SICOMP special issue
(regretfully declined).

The Computational Hardness of
Estimating Edit Distance (with Robert Krauthgamer).
In FOCS'07, and SICOMP special issue 2010.

NearOptimal Hashing Algorithms for
Approximate Nearest Neighbor in High Dimensions (with Piotr
Indyk).
Communications of the ACM, 2008.
Teaching (gradlevel classes):
Advising:
I have the pleasure to advise a number of brilliant researchers, including:
Students:
Former students, postdocs, and interns:
Lectures and talks:

Public lecture on Geometry of
Similarity Search [as pdf] at
the Simons Foundation.

Talk on Datadependent 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
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.
Other (i.e., random stuff):
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 :).