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.
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.