Publications for Eric Price

Eric Price's Publications

Spectral guarantees for adversarial streaming PCA [arXiv]
Eric Price and Zhiyang Xun
FOCS 2024
Beyond Catoni: Sharper Rates for Heavy-Tailed and Robust Mean Estimation [arXiv]
Shivam Gupta, Samuel B. Hopkins, and Eric Price
COLT 2024
Diffusion Posterior Sampling is Computationally Intractable [arXiv]
Shivam Gupta, Ajil Jalal, Aditya Parulekar, Eric Price, and Zhiyang Xun
ICML 2024
Sample-Efficient Training for Diffusion [arXiv]
Shivam Gupta, Aditya Parulekar, Eric Price, and Zhiyang Xun
NeurIPS 2024
Sharp Noisy Binary Search with Monotonic Probabilities [arXiv]
Lucas Gretta and Eric Price
ICALP 2024
Learning a 1-layer conditional generative model in total variation
Ajil Jalal, Justin Kang, Ananya Uppal, Kannan Ramchandran, and Eric Price
NeurIPS 2023
A Competitive Algorithm for Agnostic Active Learning [arXiv]
Yihan Zhou and Eric Price
NeurIPS 2023
Minimax-Optimal Location Estimation
Shivam Gupta, Jasper C.H. Lee, Eric Price, and Paul Valiant
NeurIPS 2023
Finite-Sample Symmetric Mean Estimation with Fisher Information Rate [arXiv]
Shivam Gupta, Jasper C.H. Lee, and Eric Price
COLT 2023
High-dimensional Location Estimation via Norm Concentration for Subgamma Vectors [arXiv]
Shivam Gupta, Jasper C.H. Lee, and Eric Price
ICML 2023
Fast splitting algorithms for sparsity-constrained and noisy group testing [arXiv]
Eric Price, Jon Scarlett, and Nelvin Tan
Information and Inference: A Journal of the IMA 2023
An Improved Online Reduction from PAC Learning to Mistake-Bounded Learning
Lucas Gretta and Eric Price
SOSA 2023
Finite-Sample Maximum Likelihood Estimation of Location [arXiv]
Shivam Gupta, Jasper C.H. Lee, Eric Price, and Paul Valiant
NeurIPS 2022
Linear Bandit Algorithms with Sublinear Time Complexity
Shuo Yang, Tongzheng Ren, Sanjay Shakkottai, Eric Price, Inderjit Dhillon, and Sujay Sanghavi
ICML 2022
Hardness and Algorithms for Robust and Sparse Optimization
Eric Price, Sandeep Silwal, and Samson Zhou
ICML 2022
Factorial Lower Bounds for (Almost) Random Order Streams [arXiv]
Ashish Chiplunkar, John Kallaugher, Michael Kapralov, and Eric Price
FOCS 2022
Sharp Constants in Uniformity Testing via the Huber Statistic [arXiv]
Shivam Gupta and Eric Price
COLT 2022
Coresets for Data Discretization and Sine Wave Fitting [arXiv]
Alaa Maalouf, Murad Tukan, Eric Price, Daniel Kane, and Dan Feldman
AISTATS 2022
Simulating Random Walks in Random Streams [arXiv]
John Kallaugher, Michael Kapralov, and Eric Price
SODA 2022
Robust Compressed Sensing MRI with Deep Generative Priors [arXiv]
Ajil Jalal, Marius Arvinte, Giannis Daras, Eric Price, Alex Dimakis, and Jonathan I. Tamir
NeurIPS 2021
L1 Regression with Lewis Weights Subsampling [arXiv]
Aditya Parulekar, Advait Parulekar, and Eric Price
RANDOM 2021
A Simple Proof of a New Set Disjointness with Applications to Data Streams [arXiv]
Akshay Kamath, Eric Price, and David P. Woodruff
CCC 2021
Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes [arXiv]
Wei Heng Bay, Eric Price, and Jon Scarlett
Information and Inference 2021
Fairness for Image Generation with Uncertain Sensitive Attributes [arXiv]
Ajil Jalal, Sushrut Karmalkar, Jessica Hoffman, Alex Dimakis, and Eric Price
ICML 2021
Instance-Optimal Compressed Sensing via Posterior Sampling [arXiv]
Ajil Jalal, Sushrut Karmalkar, Alex Dimakis, and Eric Price
ICML 2021
Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu [arXiv]
Arnab Bhattacharyya, Sutanu Gayen, Eric Price, and N. V. Vinodchandran
STOC 2021
Optimal Testing of Discrete Distributions with High Probability [arXiv]
Ilias Diakonikolas, Themis Gouleakis, Daniel Kane, John Peebles, and Eric Price
STOC 2021
A Fast Binary Splitting Approach to Non-Adaptive Group Testing [arXiv]
Eric Price and Jon Scarlett
RANDOM 2020
Lower Bounds for Compressed Sensing with Generative Models [arXiv]
Akshay Kamath, Sushrut Karmalkar, and Eric Price
ICML 2020
Separations and equivalences between turnstile streaming and linear sketching [arXiv]
John Kallaugher and Eric Price
STOC 2020
Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering [arXiv]
Ilias Diakonikolas, Daniel Kane, Sushrut Karmalkar, Eric Price, and Alistair Stewart
NeurIPS 2019
Adversarial examples from computational constraints [Merger of arXiv and arXiv]
Sébastien Bubeck, Yin Tat Lee, Eric Price, and Ilya Razenshteyn
ICML 2019
Active Regression via Linear-Sample Sparsification [arXiv]
Xue Chen and Eric Price
COLT 2019
Estimating the frequency of a clustered signal [arXiv]
Xue Chen and Eric Price
ICALP 2019
The Complexity of Counting Cycles in the Adjacency List Streaming Model
John Kallaugher, Andrew McGregor, Eric Price, and Sofya Vorotnikova
PODS 2019
Adaptive Sparse Recovery with Limited Adaptivity [slides]
Akshay Kamath and Eric Price
SODA 2019
Compressed Sensing with Adversarial Sparse Noise via L1 Regression [arXiv]
Sushrut Karmalkar and Eric Price
SOSA 2019
The Sketching Complexity of Graph and Hypergraph Counting [arXiv]
Michael Kapralov, John Kallaugher, and Eric Price
FOCS 2018
AmbientGAN: Generative Models From Lossy Measurements
Ashish Bora, Alex Dimakis, and Eric Price
ICLR 2018
Sample-Optimal Identity Testing with High Probability [arXiv]
Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price
ICALP 2018
Stochastic Multi-armed Bandits in Constant Space [arXiv]
David Liau, Eric Price, Zhao Song, and Ger Yang
AISTATS 2018
Robust polynomial regression up to the information theoretic limit [arXiv]
Daniel Kane, Sushrut Karmalkar, and Eric Price
FOCS 2017
Testing Hereditary Properties of Sequences
Cody Freitag, Eric Price, and William Swartworth
RANDOM 2017
Compressed Sensing using Generative Models [arXiv]
Ashish Bora, Ajil Jalal, Eric Price, and Alex Dimakis
ICML 2017
Fast Regression with an l_∞ Guarantee [arXiv]
Eric Price, Zhao Song, and David P. Woodruff
ICALP 2017
Fast Sparse Recovery for Any RIP-1 Matrix
Eric Price
ICASSP 2017 special session
A Hybrid Sampling Scheme for Triangle Counting [arXiv]
John Kallaugher and Eric Price
SODA 2017
Equality of Opportunity in Supervised Learning [arXiv]
Moritz Hardt, Eric Price, and Nathan Srebro
NIPS 2016
Fourier-sparse interpolation without a frequency gap [arXiv]
Xue Chen, Daniel Kane, Eric Price, and Zhao Song
FOCS 2016
A Robust Sparse Fourier Transform in the Continuous Setting [arXiv]
Eric Price and Zhao Song
FOCS 2015
Binary Embedding: Fundamental Limits and Fast Algorithm [arXiv]
Xinyang Yi, Constantine Caramanis, and Eric Price
ICML 2015
Tight Bounds for Learning a Mixture of Two Gaussians [slides] [notes] [arXiv]
Moritz Hardt and Eric Price
STOC 2015
SCRAM: Scalable Collision-avoiding Role Assignment with Minimal-makespan for Formational Positioning
Patrick MacAlpine, Eric Price, and Peter Stone
AAAI 2015
The Noisy Power Method: A Meta Algorithm with Applications [slides] [arXiv]
Moritz Hardt and Eric Price
NIPS 2014
Trace Reconstruction Revisited
Andrew McGregor, Eric Price, and Sofya Vorotnikova
ESA 2014
(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 [arXiv] [slides]
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] [code] [website]
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