I am broadly interested in algorithms and lower bounds. I particularly focus on really efficient algorithms — as inputs get larger, even quadratic algorithms are typically too slow. We would like our algorithms to take nearly linear or even sublinear time and space.
Sublinear algorithms are tricky, though — you can't even read or store the whole input. Much of my research has focused on compressive sensing and sparse recovery, where you want to estimate a vector from a small linear "sketch" of it. One important subtopic is sparse Fourier transforms, where we showed how to estimate the Fourier transform in less time than the FFT for sparse data.
Another aspect of my research is lower bounds. For many of the above problems and other statistical problems, we can achieve matching (or nearly matching) lower bounds on the sample complexity or space complexity. This lets us know when to stop looking for better algorithms, and to instead look for better problems.
|Fall 2017:||Algorithms and Complexity (CS 331).|
|Fall 2017:||Randomized Algorithms (CS 388R), a graduate course.|
|Spring 2017:||Honors introduction to algorithms (CS 331H).|
|Fall 2016:||Sublinear Algorithms (CS 395T), a graduate topics course.|
|Spring 2016:||Honors introduction to algorithms (CS 331H).|
|Fall 2015:||Randomized Algorithms (CS 388R), a graduate course.|
|Fall 2014:||Sublinear Algorithms (CS 395T), a graduate topics course.|
I ran the Algorithms and Complexity Seminar at MIT.
I am a coach for USACO, the USA Computer Olympiad. This program provides an excellent algorithms education for high school students.