Gregory Valiant

Affiliations:
  • University of California, Berkeley, USA


According to our database1, Gregory Valiant authored at least 95 papers between 2008 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis.
Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances.
CoRR, 2023

Testing with Non-identically Distributed Samples.
CoRR, 2023

Lexinvariant Language Models.
CoRR, 2023

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

Online Pen Testing.
Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract).
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, 2023

One-sided Matrix Completion from Two Observations Per Row.
Proceedings of the International Conference on Machine Learning, 2023

2022
From Sand to Flour: The Next Leap in Granular Computing with NanoSort.
CoRR, 2022

On the Statistical Complexity of Sample Amplification.
CoRR, 2022

What Can Transformers Learn In-Context? A Case Study of Simple Function Classes.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Efficient Convex Optimization Requires Superlinear Memory.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales.
Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021
Stronger calibration lower bounds via sidestepping.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Sinkhorn Label Allocation: Semi-Supervised Classification via Annealed Self-Training.
Proceedings of the 38th International Conference on Machine Learning, 2021

Exponential Weights Algorithms for Selective Learning.
Proceedings of the Conference on Learning Theory, 2021

Misspecification in Prediction Problems and Robustness via Improper Learning.
Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

Beyond Laurel/Yanny: An Autoencoder-Enabled Search for Polyperceivable Audio.
Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, 2021

2020
Worst-Case Analysis for Randomly Collected Data.
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.
Proceedings of the 37th International Conference on Machine Learning, 2020

Sample Amplification: Increasing Dataset Size even when Learning is Impossible.
Proceedings of the 37th International Conference on Machine Learning, 2020

Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process.
Proceedings of the Conference on Learning Theory, 2020

Sublinear Optimal Policy Value Estimation in Contextual Bandits.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

Instance Optimal Distribution Testing and Learning.
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?
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.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2013

Computation in anonymous networks.
CoRR, 2013

Testing <i>k</i>-Modal Distributions: Optimal Algorithms via Reductions.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
Algorithmic Approaches to Statistical Questions.
PhD thesis, 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.
Electron. Colloquium Comput. Complex., 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.
Electron. Colloquium Comput. Complex., 2010

A CLT and tight lower bounds for estimating entropy.
Electron. Colloquium Comput. Complex., 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


  Loading...