Publications (34)
Lower Bounds for Sparse Recovery
Khanh Do Ba, Piotr Indyk, Eric Price +1
Nearly Optimal Sparse Fourier Transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi +1
Optimal Identity Testing with High Probability
Ilias Diakonikolas, Themis Gouleakis, John Peebles +1
Fourier-sparse interpolation without a frequency gap
Xue Chen, Daniel M. Kane, Eric Price +1
A Robust Sparse Fourier Transform in the Continuous Setting
Eric Price, Zhao Song
Stochastic Multi-armed Bandits in Constant Space
David Liau, Eric Price, Zhao Song +1
Fast Regression with an $\ell_\infty$ Guarantee
Eric Price, Zhao Song, David P. Woodruff
Compressive Sensing with Local Geometric Features
Rishi Gupta, Piotr Indyk, Eric Price +1
Compressed Sensing using Generative Models
Ashish Bora, Ajil Jalal, Eric Price +1
The Sketching Complexity of Graph and Hypergraph Counting
John Kallaugher, Michael Kapralov, Eric Price
Robust polynomial regression up to the information theoretic limit
Daniel Kane, Sushrut Karmalkar, Eric Price
The Noisy Power Method: A Meta Algorithm with Applications
Moritz Hardt, Eric Price
Improved Concentration Bounds for Count-Sketch
Gregory T. Minton, Eric Price
Compressed Sensing with Adversarial Sparse Noise via L1 Regression
Sushrut Karmalkar, Eric Price
A Hybrid Sampling Scheme for Triangle Counting
John Kallaugher, Eric Price
Active Regression via Linear-Sample Sparsification
Xue Chen, Eric Price
Adversarial examples from computational constraints
Sébastien Bubeck, Eric Price, Ilya Razenshteyn
Equality of Opportunity in Supervised Learning
Moritz Hardt, Eric Price, Nathan Srebro
On the Power of Adaptivity in Sparse Recovery
Piotr Indyk, Eric Price, David P. Woodruff
Adversarial Examples from Cryptographic Pseudo-Random Generators
Sébastien Bubeck, Yin Tat Lee, Eric Price +1
Efficient Sketches for the Set Query Problem
Eric Price
Tight bounds for learning a mixture of two gaussians
Moritz Hardt, Eric Price
Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching
Arturs Backurs, Piotr Indyk, Eric Price +2
K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance
Piotr Indyk, Eric Price
Lower Bounds for Adaptive Sparse Recovery
Eric Price, David P. Woodruff
Batch Sparse Recovery, or How to Leverage the Average Sparsity
Alexandr Andoni, Lior Kamma, Robert Krauthgamer +1
Estimating the Frequency of a Clustered Signal
Xue Chen, Eric Price
New constructions of RIP matrices with fast multiplication and fewer rows
Jelani Nelson, Eric Price, Mary Wootters
Extensions and Limitations of the Neural GPU
Eric Price, Wojciech Zaremba, Ilya Sutskever
Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk +3
Binary Embedding: Fundamental Limits and Fast Algorithm
Xinyang Yi, Constantine Caramanis, Eric Price
Collision-based Testers are Optimal for Uniformity and Closeness
Ilias Diakonikolas, Themis Gouleakis, John Peebles +1
(1+eps)-approximate Sparse Recovery
Eric Price, David P. Woodruff
Optimal Lower Bound for Itemset Frequency Indicator Sketches
Eric Price