# Gregory Valiant

According to our database

Collaborative distances:

^{1}, Gregory Valiant authored at least 54 papers between 2006 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

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

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

J. ACM, 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

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

Memory, Communication, and Statistical Queries.

Proceedings of the 29th Conference on Learning Theory, 2016

2015

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

J. ACM, 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

An Automatic Inequality Prover and Instance Optimal Identity Testing.

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 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

Testing

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

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

Proceedings of the Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013

2012

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

TinyToCS, 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 Exchanges, 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

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

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

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

2006

Braess's paradox in large random graphs.

Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006