Eric Price

Associate Professor
Email:	`ecprice@cs.utexas.edu`
Office:	GDC 4.510
Postal:	Department of Computer Science University of Texas at Austin 2317 Speedway, Stop D9500 Austin, Texas 78712

Contact
Biography
Research
Teaching (current)
Publications
Misc
Awards

Biography

I am an associate 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.

Starting Fall 2024, I am on leave at Microsoft AI.

(CV)

Research

My research explores the fundamental limits of data-limited computational problems. How efficiently can we recover signals from noisy samples? And how much space do we need to compute functions of large data streams? My work has given algorithms with tight, or near-tight, sample complexities for a variety of such problems, along with corresponding lower bounds.

Examples areas of my research include:

My thesis was on sparse Fourier transforms, where one wants to estimate a sparse signal from a small number of Fourier measurements. Our algorithm was not only sample-efficient but fast: because it does not need to look at the entire input, it can beat the FFT on inputs with any sublinear sparsity level. More recently in this area I have studied signals that are sparse in the continuous domain (with and without a "frequency gap").
How should we combine compressed sensing with the deep learning revolution in image processing? We gave a provable guarantee in for using deep generative models for compressed sensing, as well as studied how to learn the generative model from noisy measurements.
When unlabeled data is cheap and labelling it is expensive, which points are most valuable to label? We gave an optimal algorithm for this problem in agnostic least squares linear regression.
What is the space complexity required for streaming algorithms, particularly graph problems? We gave new lower bounds for triangle counting, which led to new separations between standard models of streaming computation.

One nice feature of sample and space complexity is that (unlike time complexity) we have the tools to prove matching lower bounds. A large portion of my research is on proving such lower bounds. Strong lower bounds give us a target to aim for, guide how algorithms should be designed, and tell us when to stop looking for better algorithms and instead look for better problems.

You can find my list of publications here.