# Gregory Valiant

According to our database

Collaborative distances:

^{1}, Gregory Valiant authored at least 74 papers between 2008 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2020

On the Generalization Effects of Linear Transformations in Data Augmentation.

CoRR, 2020

Sublinear Optimal Policy Value Estimation in Contextual Bandits.

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

2019

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

CoRR, 2019

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

CoRR, 2019

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

CoRR, 2019

Memory-sample tradeoffs for linear regression with small error.

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

Making AI Forget You: Data Deletion in Machine Learning.

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.

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.

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

Equivariant Transformer Networks.

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

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

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

A Theory of Selective Prediction.

Proceedings of the Conference on Learning Theory, 2019

A Surprising Density of Illusionable Natural Speech.

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

2018

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

CoRR, 2018

Prediction with a short memory.

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

Sketching Linear Classifiers over Data Streams.

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

Estimating Learnability in the Sublinear Data Regime.

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.

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.

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.

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

Learning Discrete Distributions from Untrusted Batches.

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

Recovering Structured Probability Matrices.

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

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

Proceedings of the Conference On Learning Theory, 2018

2017

An Automatic Inequality Prover and Instance Optimal Identity Testing.

SIAM J. Comput., 2017

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

J. ACM, 2017

Finding Heavily-Weighted Features in Data Streams.

CoRR, 2017

Optimally Learning Populations of Parameters.

CoRR, 2017

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

CoRR, 2017

Learning from untrusted data.

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

Learning Populations of Parameters.

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

Learning Overcomplete HMMs.

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.

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

Estimating the unseen from multiple populations.

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

2016

Information Theoretically Secure Databases.

Electronic Colloquium on Computational Complexity (ECCC), 2016

Spectrum Estimation from Samples.

CoRR, 2016

Instance optimal learning of discrete distributions.

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

Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction.

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.

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.

J. ACM, 2015

Memory, Communication, and Statistical Queries.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Instance Optimal Learning.

CoRR, 2015

Testing Closeness With Unequal Sized Samples.

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.

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

Learning Sparse Polynomial Functions.

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

Learning Polynomials with Neural Networks.

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

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

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

Satisfiability and Evolution.

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

2013

Instance-by-instance optimal identity testing.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Computation in anonymous networks.

CoRR, 2013

Testing

*k*-Modal Distributions: Optimal Algorithms via Reductions.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

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

Tiny Trans. Comput. Sci., 2012

Size and Treewidth Bounds for Conjunctive Queries.

J. ACM, 2012

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

Electronic Colloquium on Computational Complexity (ECCC), 2012

Disentangling Gaussians.

Commun. ACM, 2012

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

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

2011

When is it best to best-respond?

SIGecom Exch., 2011

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

CoRR, 2011

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

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

Best-response auctions.

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

Incentive-compatible distributed greedy protocols.

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

Best-Response Mechanisms.

Proceedings of the Innovations in Computer Science, 2011

The Power of Linear Estimators.

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

2010

Designing Network Protocols for Good Equilibria.

SIAM J. Comput., 2010

Braess's Paradox in large random graphs.

Random Struct. Algorithms, 2010

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

Electronic Colloquium on Computational Complexity (ECCC), 2010

A CLT and tight lower bounds for estimating entropy.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Efficiently learning mixtures of two Gaussians.

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

On Learning Algorithms for Nash Equilibria.

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

A New Look at Selfish Routing.

Proceedings of the Innovations in Computer Science, 2010

Settling the Polynomial Learnability of Mixtures of Gaussians.

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

2009

Size Bounds for Conjunctive Queries with General Functional Dependencies

CoRR, 2009

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

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

Size and treewidth bounds for conjunctive queries.

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

2008

Designing networks with good equilibria.

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008