# Ilya Razenshteyn

## GENERAL INFORMATION

I am a researcher in the Machine Learning and Optimization group at Microsoft Research Redmond.

## NEWS

*05/17/19:*I have given a talk**“Extension theorems, dimension reduction, and clustering”**at Simons Collaboration on Algorithms & Geometry Annual Meeting*04/21/19:*One paper accepted to ICML 2019*04/18/19:*One paper accepted to COLT 2019*04/03/19:*New paper**“SANNS: Scaling Up Secure Approximate $k$-Nearest Neighbors Search”***02/11/19:*One paper accepted to STOC 2019*02/07/19:*New paper**“On Mean Estimation for General Norms with Statistical Queries”***01/26/19:*New paper**“Learning Sublinear-Time Indexing for Nearest Neighbor Search”***12/25/18:*The video of my talk**“New Algorithms for High-Dimensional Data”**is up. It is a coherent overview of my research as of beginning of 2017*12/07/18:*I am looking for**two interns to work on privacy-preserving machine learning:**apply soon!*11/29/18:*I have given a talk**“Hölder Homeomorphisms and Approximate Nearest Neighbors”**at Simons Institute (video).*11/15/18:*New paper**“Adversarial Examples from Cryptographic Pseudo-Random Generators”***11/08/18:*New paper**“Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering”**; see the talk given by Yury Makarychev at Simons Institute.*09/13/18:*I have created a webpage for the class**“Algorithms through geometric lens”**I will be teaching this Fall. (See also the previous offering.)*09/10/18:*I have given a talk**“Hölder Homeomorphisms and Approximate Nearest Neighbors”**at the Harvard Theory of Computation Seminar (slides).*08/31/18:*I have given a tutorial on nearest neighbor search at the Foundations of the Data Science Bootcamp at Simons Institute: part 1, part 2.*08/13/18:*An article in Quanta Magazine covering some of my recent work.

## SELECTED PUBLICATIONS

- S. Bubeck, Y.T. Lee, E. Price and IR,
**Adversarial examples from computational constraints**,*ICML*, 2019 (arXiv + arXiv).

Accepted as a long talk -
K. Makarychev, Y. Makarychev and IR,
**Performance of Johnson—Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering**,*STOC*, 2019 (arXiv).

Invited to the special issue of Theory of Computing - A. Andoni, A. Naor, A. Nikolov, IR and E. Waingarten,
**Hölder Homeomorphisms and Approximate Nearest Neighbors**,*FOCS*, 2018 (local copy). - A. Andoni, A. Naor, A. Nikolov, IR and E. Waingarten,
**Data-Dependent Hashing via Nonlinear Spectral Gaps**,*STOC*, 2018 (local copy). -
A. Andoni, T. Laarhoven, IR and E. Waingarten,
**Optimal Hashing-based Time–Space Trade-offs for Approximate Near Neighbors**,*SODA*, 2017 (arXiv).

Invited to the special issue of ACM Transactions on Algorithms -
A. Andoni, P. Indyk, T. Laarhoven, IR and L. Schmidt,
**Practical and Optimal LSH for Angular Distance**,*NIPS*, 2015 (arXiv). -
A. Andoni and IR,
**Optimal Data-Dependent Hashing for Approximate Near Neighbors**,*STOC*, 2015 (arXiv).

Invited to Highlights of Algorithms (HALG 2016) -
A. Andoni, R. Krauthgamer and IR,
**Sketching and Embedding are Equivalent for Norms**,*STOC*, 2015 (arXiv).

Appeared in the special issue of SIAM Journal on Computing

Invited to Highlights of Algorithms (HALG 2016)

See the full list of papers (with slides, posters, videos etc).

## TRIVIA

During Fall 2017, I was a Simons Junior Fellow at Columbia University hosted by Alexandr Andoni.
In August 2017 I graduated with Ph.D. in Computer Science from MIT Computer Science and AI Laboratory, where
I was privileged to be advised by
Piotr Indyk.
Check out my thesis **“High-Dimensional Similarity Search and Sketching: Algorithms and Hardness”**.
I graduated in June 2012 from Moscow State University with B.S. in Mathematics;
my advisors were great Maxim Babenko and Sasha Shen.

- Email:
**ilyaraz@mit.edu**,**ilyaraz@microsoft.com** - My CV (as of July 2, 2018)
- My Google Scholar profile
- My research statement (as of December 2016)

I do Theoretical Computer Science. My research interests are revolving around efficient algorithms for massive datasets with geometric structure.

**I help organizing TCS+: a series of online seminars in Theory.
Watch some of the past talks: the speaker list can easily compete with any offline seminar I know of!** If you want to suggest a speaker, fill a form.

My wife does Theory as well!

**Program Committees:** STOC 2019, SODA 2019, CSR 2018, SEA 2016.

## VIDEOS OF MY TALKS

- “Hölder Homeomorphisms and Approximate Nearest Neighbors” (Simons Institute)
- A tutorial on the nearest neighbor search: part 1, part 2 (Foundations of Data Science Bootcamp @ Simons Institute)
- “Beyond John's Ellipsoid” (Learning and Optimization workshop at MSR)
- “Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors” (CMU Theory Lunch)
- “Sketching and Embedding are Equivalent for Norms” (TCS+)
- “Locality-Sensitive Hashing and Beyond” (Microsoft Research)

## CODE

- FALCONN: a highly optimized C++ library (with Python bindings) for similarity search based on LSH.
- QuadSketch: a simple and fast algorithm for compressing Euclidean metrics.
- pytorch_kmeans: implementation of the k-means algorithm in PyTorch that works for large datasets.

## TEACHING

- Fall 2018: The second incarnation of Algorithms through Geometric Lens, University of Washington.
- Fall 2017: co-teaching (with Alexandr Andoni) a class Algorithms through Geometric Lens, Columbia University.
- May 2017: mini-course Algorithms for high-dimensional data at the school Recent Advances in Algorithms, Saint Petersburg.
- January 2016: mini-course From “compact presentations” to algorithms for big data at PDMI CS Club (me and students who took the class)
- Fall 2015: TA for Introduction to Algorithms (6.006) at MIT (taught by Piotr Indyk and Ron Rivest)
- Spring 2014: TA for the Piotr Indyk's course Geometric Computing (6.850) at MIT
- Spring 2011: TA for the Andrew Goldberg's mini-course Path and Flow Algorithms at Yandex Data Analysis School

© 2015–2018