Eric Price

CoRR, 2023

An Improved Online Reduction from PAC Learning to Mistake-Bounded Learning.

[BibT_eX]

[DOI]

Lucas Gretta

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

A Competitive Algorithm for Agnostic Active Learning.

[BibT_eX]

[DOI]

Yihan Zhou

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Learning a 1-layer conditional generative model in total variation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Minimax-Optimal Location Estimation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

High-dimensional Location Estimation via Norm Concentration for Subgamma Vectors.

[BibT_eX]

[DOI]

Shivam Gupta

Jasper C. H. Lee

Proceedings of the International Conference on Machine Learning, 2023

Finite-Sample Symmetric Mean Estimation with Fisher Information Rate.

[BibT_eX]

[DOI]

Shivam Gupta

Jasper C. H. Lee

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Simulating Random Walks in Random Streams.

[BibT_eX]

[DOI]

Michael Kapralov

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Finite-Sample Maximum Likelihood Estimation of Location.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Linear Bandit Algorithms with Sublinear Time Complexity.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2022

Hardness and Algorithms for Robust and Sparse Optimization.

[BibT_eX]

[DOI]

Sandeep Silwal

Samson Zhou

Proceedings of the International Conference on Machine Learning, 2022

Factorial Lower Bounds for (Almost) Random Order Streams.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Sharp Constants in Uniformity Testing via the Huber Statistic.

[BibT_eX]

[DOI]

Shivam Gupta

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Coresets for Data Discretization and Sine Wave Fitting.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Approximating Local Graph Structure in Almost Random Order Streams.

[BibT_eX]

[DOI]

CoRR, 2021

Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing.

[BibT_eX]

[DOI]

Jonathan Scarlett

Nelvin Tan

CoRR, 2021

Near-optimal learning of tree-structured distributions by Chow-Liu.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Robust Compressed Sensing MRI with Deep Generative Priors.

[BibT_eX]

[DOI]

Jonathan I. Tamir

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Fairness for Image Generation with Uncertain Sensitive Attributes.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Instance-Optimal Compressed Sensing via Posterior Sampling.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

A Simple Proof of a New Set Disjointness with Applications to Data Streams.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

L1 Regression with Lewis Weights Subsampling.

[BibT_eX]

[DOI]

Aditya Parulekar

Advait Parulekar

Proceedings of the Approximation, 2021

2020

Optimal Testing of Discrete Distributions with High Probability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Separations and equivalences between turnstile streaming and linear sketching.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

On the Power of Compressed Sensing with Generative Models.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

A Fast Binary Splitting Approach to Non-Adaptive Group Testing.

[BibT_eX]

[DOI]

Jonathan Scarlett

Proceedings of the Approximation, 2020

Sparse Recovery.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019

Lower Bounds for Compressed Sensing with Generative Models.

[BibT_eX]

[DOI]

CoRR, 2019

Exponential Separations Between Turnstile Streaming and Linear Sketching.

[BibT_eX]

[DOI]

CoRR, 2019

Collision-Based Testers are Optimal for Uniformity and Closeness.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2019

Compressed Sensing with Adversarial Sparse Noise via L1 Regression.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

Adaptive Sparse Recovery with Limited Adaptivity.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

The Complexity of Counting Cycles in the Adjacency List Streaming Model.

[BibT_eX]

[DOI]

Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2019

Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filtering.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Adversarial examples from computational constraints.

[BibT_eX]

[DOI]

Proceedings of the 36th International Conference on Machine Learning, 2019

Estimating the Frequency of a Clustered Signal.

[BibT_eX]

[DOI]

Xue Chen

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Active Regression via Linear-Sample Sparsification.

[BibT_eX]

[DOI]

Xue Chen

Proceedings of the Conference on Learning Theory, 2019

2018

Adversarial Examples from Cryptographic Pseudo-Random Generators.

[BibT_eX]

[DOI]

CoRR, 2018

Batch Sparse Recovery, or How to Leverage the Average Sparsity.

[BibT_eX]

[DOI]

CoRR, 2018

Compressed Sensing with Deep Image Prior and Learned Regularization.

[BibT_eX]

[DOI]

CoRR, 2018

Adversarial examples from computational constraints.

[BibT_eX]

[DOI]

Sébastien Bubeck

Ilya P. Razenshteyn

CoRR, 2018

AmbientGAN: Generative models from lossy measurements.

[BibT_eX]

[DOI]

Ashish Bora

Proceedings of the 6th International Conference on Learning Representations, 2018

The Sketching Complexity of Graph and Hypergraph Counting.

[BibT_eX]

[DOI]

Michael Kapralov

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Stochastic Multi-armed Bandits in Constant Space.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2018

2017

Sample-Optimal Identity Testing with High Probability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Condition number-free query and active learning of linear families.

[BibT_eX]

[DOI]

Xue Chen

CoRR, 2017

Fast Regression with an $\ell_\infty$ Guarantee.

[BibT_eX]

[DOI]

Zhao Song

CoRR, 2017

A Hybrid Sampling Scheme for Triangle Counting.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Compressed Sensing using Generative Models.

[BibT_eX]

[DOI]

Ashish Bora

Ajil Jalal

Proceedings of the 34th International Conference on Machine Learning, 2017

Fast sparse recovery for any RIP-1 matrix.

[BibT_eX]

[DOI]

Proceedings of the 2017 IEEE International Conference on Acoustics, 2017

Fast Regression with an $ell_infty$ Guarantee.

[BibT_eX]

[DOI]

Zhao Song

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Robust Polynomial Regression up to the Information Theoretic Limit.

[BibT_eX]

[DOI]

Daniel Kane

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Testing Hereditary Properties of Sequences.

[BibT_eX]

[DOI]

Cody R. Freitag

William J. Swartworth

Proceedings of the Approximation, 2017

2016

Sparse Fourier Transform.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Extensions and Limitations of the Neural GPU.

[BibT_eX]

[DOI]

Wojciech Zaremba

Ilya Sutskever

CoRR, 2016

Improved graph sampling for triangle counting.

[BibT_eX]

[DOI]

CoRR, 2016

Equality of Opportunity in Supervised Learning.

[BibT_eX]

[DOI]

Nati Srebro

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Fourier-Sparse Interpolation without a Frequency Gap.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Nearly-optimal bounds for sparse recovery in generic norms, with applications to $k$-median sketching.

[BibT_eX]

[DOI]

CoRR, 2015

Tight Bounds for Learning a Mixture of Two Gaussians.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Binary Embedding: Fundamental Limits and Fast Algorithm.

[BibT_eX]

[DOI]

Xinyang Yi

Constantine Caramanis

Proceedings of the 32nd International Conference on Machine Learning, 2015

A Robust Sparse Fourier Transform in the Continuous Setting.

[BibT_eX]

[DOI]

Zhao Song

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

SCRAM: Scalable Collision-avoiding Role Assignment with Minimal-Makespan for Formational Positioning.

[BibT_eX]

[DOI]

Patrick MacAlpine

Peter Stone

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014

Optimal Lower Bound for Itemset Frequency Indicator Sketches.

[BibT_eX]

[DOI]

CoRR, 2014

Sharp bounds for learning a mixture of two gaussians.

[BibT_eX]

[DOI]

CoRR, 2014

New constructions of RIP matrices with fast multiplication and fewer rows.

[BibT_eX]

[DOI]

Jelani Nelson

Mary Wootters

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Improved Concentration Bounds for Count-Sketch.

[BibT_eX]

[DOI]

Gregory T. Minton

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

(Nearly) Sample-Optimal Sparse Fourier Transform.

[BibT_eX]

[DOI]

Michael Kapralov

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

The Noisy Power Method: A Meta Algorithm with Applications.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, 2014

Trace Reconstruction Revisited.

[BibT_eX]

[DOI]

Andrew McGregor

Sofya Vorotnikova

Proceedings of the Algorithms - ESA 2014, 2014

2013

Sparse recovery and Fourier sampling.

[BibT_eX]

[DOI]

Eric C. Price

PhD thesis, 2013

Lower Bounds for Adaptive Sparse Recovery.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Sample-optimal average-case sparse Fourier Transform in two dimensions.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual Allerton Conference on Communication, 2013

2012

Compressive Sensing with Local Geometric Features.

[BibT_eX]

[DOI]

Int. J. Comput. Geom. Appl., 2012

Nearly optimal sparse fourier transform.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Simple and practical algorithm for sparse Fourier transform.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Applications of the Shannon-Hartley theorem to data streams and sparse recovery.

[BibT_eX]

[DOI]

Proceedings of the 2012 IEEE International Symposium on Information Theory, 2012

2011

K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Efficient Sketches for the Set Query Problem.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

(1 + eps)-Approximate Sparse Recovery.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

On the Power of Adaptivity in Sparse Recovery.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Confluently Persistent Tries for Efficient Version Control.

[BibT_eX]

[DOI]

Erik D. Demaine

Stefan Langerman

Algorithmica, 2010

Lower Bounds for Sparse Recovery.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Sparse recovery for Earth Mover Distance.

[BibT_eX]

[DOI]

Rishi Gupta