Piotr Indyk
I am a Thomas D. and Virginia W. Cabot Professor in the Department of Electrical Engineering and
Computer Science.
I am a co-director of Foundations of Data Science Institute (FODSI).
I am also a member of Theory of
Computation Group in Computer Science
and Artificial Intelligence Lab.
Bio: (on wiki)
Code:
- FALCONN
- fast algorithm for similarity search, based on Locality Sensitive
Hashing.
- The project
web page on our Sparse FFT algorithms, with the code for sFFT 1.0 and 2.0 algorithms published in SODA'12.
Research
Interests:
High-dimensional
computational geometry (including approximate nearest neighbor search), data
stream algorithms, sparse recovery, compressive sensing, machine learning
algorithms, learning-based algorithms.
Current
students:
Past students:
- Nitin Thaper
- Javed Samuel (MEng) (NNC Group)
- Mihai Badoiu (Edgestream
Partners LP)
- David Woodruff
(Professor at CMU)
- Anastasios
Sidiropoulos (Associate Professor at University of Illinois at Chicago
and Determinant Technologies).
- Alex Andoni (Associate
Professor at Columbia University)
- Radu Berinde (MEng) (Cockroach Labs)
- Rishi Gupta
(MEng) (Airtable)
- Jelani Nelson
(Professor at UC Berkeley)
- Khanh Do Ba
- Eric Price (Associate
Professor at UT Austin)
- Elyot Grant (Lunarch)
- Sepideh Mahabadi
(Senior Researcher at Microsoft Research)
- Ilya Razenshteyn (Open AI)
- Ludwig
Schmidt (Assistant Professor at Stanford University)
- Arturs Backurs (Senior Researcher at Microsoft Research)
- Ali Vakilian (Assistant Professor at Virginia Tech)
- Tal Wagner (Assistant Professor at Tel Aviv University and Amazon)
- Nicholas Schiefer
(MS) (Anthropic)
- Sandeep Silwal (Assistant Professor at the University of
Wisconsin-Madison)
- Shyam
Narayanan (Citadel Securities)
Past postdocs:
- Julia Chuzhoy
- Jayadev
Acharya
- Mahdi Cheraghchi
- Michael
Kapralov
- Chinmay Hegde
- Yang Yuan
(supported by MIFODS)
- Talya
Eden (supported by MIFODS)
- Vaggos (Evangelos) Chatziafratis
(supported by FODSI)
- Anders Aamand
Publications:
Here
is a list of some of my papers.
Surveys,
tutorials and talks:
- Towards overcoming the reranking
bottleneck, Paul Erdos Memorial Lecture, CCCG 2025.
- Challenges and Opportunities of
Graph-Based Algorithms for Similarity Search, invited talk at SISAP
2024, ISAAC 2025.
- Approximate
nearest neighbor search in high dimensions, invited talk at the
International Congress of Mathematicians, 2018. PDF
version.
- Recent Developments in the
Sparse Fourier Transform , at ICASSP,
2015.
- Recent Developments in the
Sparse Fourier Transform , at GlobalSIP, 2013.
- Sketching via Hashing: from Heavy Hitters to
Compressive Sensing to Sparse Fourier Transform: slides
and writeup, at PODS, 2013.
- Lectures on high-dimensional near(est) neighbor search:
1 2 3 at MADALGO
& CTIC Summer School on HIGH-DIMENSIONAL GEOMETRIC COMPUTING,
2011.
- Tutorial on Sparse Recovery Using
Sparse Matrices, given at MMDS'10
and China Theory
Week, 2010.
- A survey on Sparse Recovery
Using Sparse Matrices (with A. Gilbert), Proceedings of IEEE,
2010.
- A talk on Sparse Recovery Using
Sparse Matrices, given in various forms in various places.
- A tutorial on Streaming,
Sketching and Sub-linear Space Algorithms, given at the 2009 Information Theory and
Applications Workshop, San Diego, 2009.
- A tutorial on Compressed
Sensing (or Compressive Sampling or Linear Sketching), given at the Workshop
on Geometry and Algorithms, Princeton, 2008.
- A talk on Explicit constructions
in high-dimensional geometry, given at 2007 von Neumann
Symposium on Sparse Representation and High-Dimensional Geometry,
Snowbird, 2007.
- An invited talk on Hashing,
sketching and other randomized algorithms for high-dimensional data",
given at EMNLP'07
- Two lectures on algorithms for finding nearest
neighbors in low and high
dimensions, Summer
School on Algorithmic Data Analysis, Helsinki, 2007.
- A tutorial on Low-distortion
embeddings and data structures, given at the Concentration
Week on Metric Geometry and Geometric Embeddings of Discrete Metric Spaces,
Texas A&M University, 2006.
- A talk on "Near-Optimal Hashing
Algorithms for Approximate Near(est) Neighbor Problem", given at MMDS'06: Workshop on Algorithms
for Modern Massive Data Sets, Stanford, 2006.
- Approximation Algorithms for
Embedding Problems, given at Fast Manifold Learning
Workshop, College of William and Mary, 2006.
- An invited talk on "Streaming
Algorithms for Geometric Problems" at CCCG'04, FSTTCS'04
, FOCM'05 and Sublinear Algorithms Workshop.
- A talk on Efficient Similarity
Search in High Dimensions" that I gave at LEMS, Brown University, July 2004.
- An invited talk on "Embedded Stringology" at the Symposium on Combinatorial Pattern
Matching (CPM 2004)".
- An invited talk on "Algorithmic
Applications of Low-Distortion Embeddings" at the Snowbird Learning Workshop 2004 .
- Two surveys for the upcoming 2nd edition of "CRC Handbook
of Discrete and Computational Geometry": "Nearest
Neighbors in High-dimensional Spaces" and "Low
Distortion Embeddings of Finite Metric Spaces" (with Jiri
Matousek).
- An invited talk on Approximate
Nearest Neighbor (Beyond the l_p norms) at
the International
Workshop on Designing Tomorrow's Category-Level 3D Object Recognition
Systems.
- An invited talk on "Approximate
Algorithms for High-Dimensional Geometric Problems" at the DIMACS Workshop on
Computational Geometry'02.
- A tutorial at FOCS 2001 on "Algorithmic
Aspects of Geometric Embeddings".
- A short course on "Nearest
Neighbors and Other Problems in High Dimensional Computational
Geometry" at AT&T during the summer of 1999.
Grad course materials:
Spring
2019: Learning-Augmented
Algorithms.
Fall 2017: Sketching Algorithms for Big Data (jointly with Jelani Nelson at Harvard).
Fall 2014: Algorithms and Signal Processing (6.893).
Spring 2013: Sub-linear Algorithms (6.893).
Spring 2012: Geometric Computing (6.850).
Fall 2010: Sub-linear Algorithms (6.896).
Spring 2009: Streaming Etc. (at Rice University).
Fall 2007: Sketching, Streaming, and Sub-linear Space algorithms (6.895).
Spring 2007: Geometric Computation (6.850).
Fall 2006: Computational Biology, Too (6.895/6.085).
Fall 2005: Computational Biology (6.895/6.095).
Spring 2005: Geometric Computing (6.838) .
Fall 2003: Geometric Computing (6.838) .
Fall 2002: Algorithms for Massive Data Sets (6.897).
Fall 2001: Geometric Computation (6.838)
Fall 2000: Algorithmic Aspects of Embeddings (6.978).
Projects:
Sparse Fourier Transform From Theory to Practice
Accessibility
Piotr IndykMIT Computer Science and Artificial Intelligence Lab
Room G642
32 Vassar Street
Cambridge, Massachusetts 02139
Fax: (617) 258-8682
email: indyk ατ theory.lcs.mit.edu