Eric Price

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 co-created NewsDiffs, which tracks post-publication 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) sample-optimal 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 Count-Sketch[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)
• Sample-Optimal Average-Case 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 Shannon-Hartley 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
• K-Median Clustering, Model-Based 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
• Browser-Based Attacks on Tor
  Timothy G. Abbott, Katherine J. Lai, Michael R. Lieberman, and Eric C. Price
  PET 2007