Eric Price
ecprice@mit.edu
I am a computer science researcher mainly interested in algorithms. I
am a postdoc at the Simons
Institute in Berkeley for Fall 2013 and will be at
the IBM
Almaden Research Center in Spring 2014. I will start as an
assistant professor at UT Austin
in fall 2014.
I mostly work on sparse recovery, compressive sensing,
and sparse
Fourier sampling. After writing
my thesis, I graduated in 2013
from MIT CSAIL advised
by Piotr Indyk.
(CV)
I ran the Algorithms and Complexity
Seminar at MIT.
I cocreated NewsDiffs, which tracks postpublication changes to online news articles. [slides]
Papers:

The Noisy Power Method: A Meta Algorithm with Applications
Moritz Hardt and Eric Price
Manuscript

Sharp bounds for learning a mixture of two Gaussians[slides] [arXiv]
Moritz Hardt and Eric Price
Manuscript

(Nearly) sampleoptimal sparse Fourier transform
Michael Kapralov, Eric Price, and Piotr Indyk
SODA 2014

New constructions of RIP matrices with fast multiplication and fewer rows[slides] [arXiv]
Jelani Nelson, Eric Price, and Mary Wootters
SODA 2014

Improved Concentration Bounds for CountSketch[slides] [arXiv]
Gregory T. Minton and Eric Price
SODA 2014 (Best Student Paper)

Sparse Recovery and Fourier Sampling[slides]
Eric Price
Ph.D. Thesis (George M. Sprowls Award, given for the best doctoral theses in computer science at MIT)

SampleOptimal AverageCase Sparse Fourier Transform in Two Dimensions[arXiv]
Badih Ghazi, Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price, and Lixin Shi
Allerton 2013

Lower Bounds for Adaptive Sparse Recovery[arXiv]
Eric Price and David P. Woodruff
SODA 2013

Applications of the ShannonHartley Theorem to Data Streams and Sparse Recovery
Eric Price and David P. Woodruff
ISIT 2012

Nearly Optimal Sparse Fourier Transform[slides] [arXiv] [website]
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price
STOC 2012

Simple and Practical Algorithm for Sparse Fourier Transform[slides] [website] [code]
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price
SODA 2012

On the Power of Adaptivity in Sparse Recovery[slides] [arXiv]
Piotr Indyk, Eric Price, and David P. Woodruff
FOCS 2011

(1+eps)approximate sparse recovery[arXiv]
Eric Price and David P. Woodruff
FOCS 2011

KMedian Clustering, ModelBased Compressive Sensing, and Sparse Recovery for Earth Mover Distance[arXiv]
Piotr Indyk and Eric Price
STOC 2011

Compressive Sensing with Local Geometric Features
Rishi Gupta, Piotr Indyk, Eric Price, and Yaron Rachlin
SOCG 2011

Efficient Sketches for the Set Query Problem[arXiv]
Eric Price
SODA 2011

Sparse Recovery for Earth Mover Distance[code]
Rishi Gupta, Piotr Indyk, and Eric Price
Allerton (invited paper) 2010

Lower Bounds for Sparse Recovery[arXiv]
Khanh Do Ba, Piotr Indyk, Eric Price, and David P. Woodruff
SODA 2010

Confluently Persistent Tries for Efficient Version Control
Erik Demaine, Stefan Langerman, and Eric Price
SWAT 2008

BrowserBased Attacks on Tor
Timothy G. Abbott, Katherine J. Lai, Michael R. Lieberman, and Eric C. Price
PET 2007