Gregory Valiant

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

On the Generalization Effects of Linear Transformations in Data Augmentation.

[BibT_eX]

[DOI]

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

Sample Amplification: Increasing Dataset Size even when Learning is Impossible.

[BibT_eX]

[DOI]

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

Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Sublinear Optimal Policy Value Estimation in Contextual Bandits.

[BibT_eX]

[DOI]

Emma Brunskill

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

Instance Optimal Distribution Testing and Learning.

[BibT_eX]

[DOI]

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

2019

How bad is worst-case data if you know where it comes from?

[BibT_eX]

[DOI]

Justin Y. Chen

CoRR, 2019

Memory-sample tradeoffs for linear regression with small error.

[BibT_eX]

[DOI]

Vatsal Sharan

Aaron Sidford

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Making AI Forget You: Data Deletion in Machine Learning.

[BibT_eX]

[DOI]

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

A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families.

[BibT_eX]

[DOI]

Brian Axelrod

Ilias Diakonikolas

Alistair Stewart

Anastasios Sidiropoulos

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

Maximum Likelihood Estimation for Learning Populations of Parameters.

[BibT_eX]

[DOI]

Ramya Korlakai Vinayak

Sham M. Kakade

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

Equivariant Transformer Networks.

[BibT_eX]

[DOI]

Kai Sheng Tai

Peter Bailis

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

Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data.

[BibT_eX]

[DOI]

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

A Theory of Selective Prediction.

[BibT_eX]

[DOI]

Mingda Qiao

Proceedings of the Conference on Learning Theory, 2019

A Surprising Density of Illusionable Natural Speech.

[BibT_eX]

[DOI]

Melody Y. Guan

Proceedings of the 41th Annual Meeting of the Cognitive Science Society, 2019

2018

An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood.

[BibT_eX]

[DOI]

Brian Axelrod

CoRR, 2018

Prediction with a short memory.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Sketching Linear Classifiers over Data Streams.

[BibT_eX]

[DOI]

Proceedings of the 2018 International Conference on Management of Data, 2018

Estimating Learnability in the Sublinear Data Regime.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

A Spectral View of Adversarially Robust Features.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Approximating the Spectrum of a Graph.

[BibT_eX]

[DOI]

Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018

Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers.

[BibT_eX]

[DOI]

Moses Charikar

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Learning Discrete Distributions from Untrusted Batches.

[BibT_eX]

[DOI]

Mingda Qiao

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Recovering Structured Probability Matrices.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

A Data Prism: Semi-verified learning in the small-alpha regime.

[BibT_eX]

[DOI]

Michela Meister

Proceedings of the Conference On Learning Theory, 2018

2017

An Automatic Inequality Prover and Instance Optimal Identity Testing.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Estimating the Unseen: Improved Estimators for Entropy and Other Properties.

[BibT_eX]

[DOI]

J. ACM, 2017

Finding Heavily-Weighted Features in Data Streams.

[BibT_eX]

[DOI]

CoRR, 2017

Optimally Learning Populations of Parameters.

[BibT_eX]

[DOI]

Kevin Tian

CoRR, 2017

There and Back Again: A General Approach to Learning Sparse Models.

[BibT_eX]

[DOI]

CoRR, 2017

Learning from untrusted data.

[BibT_eX]

[DOI]

Moses Charikar

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Learning Populations of Parameters.

[BibT_eX]

[DOI]

Kevin Tian

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Learning Overcomplete HMMs.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use.

[BibT_eX]

[DOI]

Vatsal Sharan

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

Estimating the unseen from multiple populations.

[BibT_eX]

[DOI]

Aditi Raghunathan

James Zou

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

2016

Information Theoretically Secure Databases.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Spectrum Estimation from Samples.

[BibT_eX]

[DOI]

CoRR, 2016

Instance optimal learning of discrete distributions.

[BibT_eX]

[DOI]

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction.

[BibT_eX]

[DOI]

Moses Charikar

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

Stochastic Streams: Sample Complexity vs. Space Complexity.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem.

[BibT_eX]

[DOI]

J. ACM, 2015

Memory, Communication, and Statistical Queries.

[BibT_eX]

[DOI]

Stefan Wager

Electron. Colloquium Comput. Complex., 2015

Instance Optimal Learning.

[BibT_eX]

[DOI]

CoRR, 2015

Testing Closeness With Unequal Sized Samples.

[BibT_eX]

[DOI]

Bhaswar B. Bhattacharya

Christos H. Papadimitriou

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

2014

Optimal Algorithms for Testing Closeness of Discrete Distributions.

[BibT_eX]

[DOI]

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

Learning Sparse Polynomial Functions.

[BibT_eX]

[DOI]

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

Learning Polynomials with Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the 31th International Conference on Machine Learning, 2014

Least Squares Revisited: Scalable Approaches for Multi-class Prediction.

[BibT_eX]

[DOI]

Proceedings of the 31th International Conference on Machine Learning, 2014

Satisfiability and Evolution.

[BibT_eX]

[DOI]

Adi Livnat

Aviad Rubinstein

Andrew Wan

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Instance-by-instance optimal identity testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Computation in anonymous networks.

[BibT_eX]

[DOI]

Elchanan Mossel

Anupam Prakash

CoRR, 2013

Testing <i>k</i>-Modal Distributions: Optimal Algorithms via Reductions.

[BibT_eX]

[DOI]

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

2012

Algorithmic Approaches to Statistical Questions.

[BibT_eX]

[DOI]

PhD thesis, 2012

Beating brute-force: Improved algorithms for finding correlations, and related problems.

[BibT_eX]

[DOI]

Adv. Math. Commun., 2012

Size and Treewidth Bounds for Conjunctive Queries.

[BibT_eX]

[DOI]

J. ACM, 2012

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Disentangling Gaussians.

[BibT_eX]

[DOI]

Adam Tauman Kalai

Ankur Moitra

Commun. ACM, 2012

Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

When is it best to best-respond?

[BibT_eX]

[DOI]

SIGecom Exch., 2011

Testing $k$-Modal Distributions: Optimal Algorithms via Reductions

[BibT_eX]

[DOI]

CoRR, 2011

Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs.

[BibT_eX]

[DOI]

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

Best-response auctions.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Incentive-compatible distributed greedy protocols.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Best-Response Mechanisms.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

The Power of Linear Estimators.

[BibT_eX]

[DOI]

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

2010

Designing Network Protocols for Good Equilibria.

[BibT_eX]

[DOI]

Ho-Lin Chen

Tim Roughgarden

SIAM J. Comput., 2010

Braess's Paradox in large random graphs.

[BibT_eX]

[DOI]

Tim Roughgarden

Random Struct. Algorithms, 2010

Estimating the unseen: A sublinear-sample canonical estimator of distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

A CLT and tight lower bounds for estimating entropy.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Efficiently learning mixtures of two Gaussians.

[BibT_eX]

[DOI]

Adam Tauman Kalai

Ankur Moitra

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

On Learning Algorithms for Nash Equilibria.

[BibT_eX]

[DOI]

Christos H. Papadimitriou

Rafael M. Frongillo

George Pierrakos

Christos H. Papadimitriou

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

A New Look at Selfish Routing.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2010

Settling the Polynomial Learnability of Mixtures of Gaussians.

[BibT_eX]

[DOI]

Ankur Moitra

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Size Bounds for Conjunctive Queries with General Functional Dependencies

[BibT_eX]

[DOI]

CoRR, 2009

On the complexity of Nash equilibria of action-graph games.

[BibT_eX]

[DOI]

Grant Schoenebeck

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Size and treewidth bounds for conjunctive queries.

[BibT_eX]

[DOI]

Georg Gottlob

Stephanie Tien Lee

Proceedings of the Twenty-Eigth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2009

2008

Designing networks with good equilibria.

[BibT_eX]

[DOI]

Ho-Lin Chen

Tim Roughgarden