Gregory Valiant

According to our database1, Gregory Valiant authored at least 99 papers between 2006 and 2019.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepage:

On csauthors.net:

Bibliography

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

Making AI Forget You: Data Deletion in Machine Learning.
CoRR, 2019

A Surprising Density of Illusionable Natural Speech.
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.
CoRR, 2019

Maximum Likelihood Estimation for Learning Populations of Parameters.
CoRR, 2019

A Theory of Selective Prediction.
CoRR, 2019

Equivariant Transformer Networks.
CoRR, 2019

Memory-sample tradeoffs for linear regression with small error.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 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
A Spectral View of Adversarially Robust Features.
CoRR, 2018

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

Estimating Learnability in the Sublinear Data Regime.
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

Approximating the Spectrum of a Graph.
CoRR, 2017

Learning Discrete Distributions from Untrusted Batches.
CoRR, 2017

Learning Overcomplete HMMs.
CoRR, 2017

Finding Heavily-Weighted Features in Data Streams.
CoRR, 2017

Optimally Learning Populations of Parameters.
CoRR, 2017

A Data Prism: Semi-Verified Learning in the Small-Alpha Regime.
CoRR, 2017

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

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

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

Estimating the unseen from multiple populations.
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

Information Theoretically Secure Databases.
CoRR, 2016

Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction.
CoRR, 2016

Spectrum Estimation from Samples.
CoRR, 2016

Prediction with a Short Memory.
CoRR, 2016

Recovering Structured Probability Matrices.
CoRR, 2016

Learning from Untrusted Data.
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

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

Memory, Communication, and Statistical Queries.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Instance Optimal Learning.
CoRR, 2015

Testing Closeness With Unequal Sized Samples.
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

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

Computation in anonymous networks.
CoRR, 2013

Optimal Algorithms for Testing Closeness of Discrete Distributions.
CoRR, 2013

Least Squares Revisited: Scalable Approaches for Multi-class Prediction.
CoRR, 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

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

Settling the Polynomial Learnability of Mixtures of Gaussians
CoRR, 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
On the Complexity of Nash Equilibria of Action-Graph Games
CoRR, 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


  Loading...