Eric Price

Assistant Professor
Office:GDC 4.510
Postal: Department of Computer Science
University of Texas at Austin
2317 Speedway, Stop D9500
Austin, Texas 78712


I am an assistant professor in the Department of Computer Science at the University of Texas at Austin. My undergraduate and graduate education was at MIT, where I was fortunate to have Piotr Indyk as my advisor. After graduating in 2013, I was a postdoc at the Simons Institute in Berkeley and at the IBM Almaden Research Center before arriving at UT in Fall 2014. (CV)


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 created and maintain NewsDiffs, which tracks post-publication changes to online news articles. [slides]

I am a coach for USACO, the USA Computer Olympiad. This program provides an excellent algorithms education for high school students.


Either look at all publications or the selected ones below:


and I used to be pretty good at math/CS contests: