My PhD dissertation, *Algorithmic Approaches to Statistical Questions,* 2012. (ACM Doctoral Dissertation Award, Honorable Mention.) [pdf]

- Annie Marsden, Vatsal Sharan, Aaron Sidford, and Gregory Valiant,
*Efficient Convex Optimization Requires Superlinear Memory.*COLT, 2022. (Best Paper Award)

[abstract] [bib] [pdf]

- Kartik Chandra, Chuma Kabaghe and Gregory Valiant,
*Beyond Laurel/Yanny: An Autoencoder-Enabled Search for Polyperceivable Audio.*ACL, 2021.

[abstract] [bib] [pdf] [examples]

- Mingda Qiao and Gregory Valiant,
*Stronger Calibration Lower Bounds via Sidestepping.*STOC, 2021.

[abstract] [bib] [arxiv]

- Annie Marsden, John Duchi and Gregory Valiant,
*Misspecification in Prediction Problems and Robustness via Improper Learning.*AISTATS, 2021. (Full oral presentation.)

[abstract] [bib] [pdf]

- Justin Y. Chen, Gregory Valiant, and Paul Valiant,
*Worst-Case Analysis for Randomly Collected Data.*NeurIPS, 2020. [Oral Presentation.]

[abstract] [bib] [pdf][Short Video (from NeurIPS'20)]

- Brian Axelrod, Shivam Garg, Vatsal Sharan, and Gregory Valiant,
*Sample Amplification: Increasing Dataset Size even when Learning is Impossible.*ICML, 2020.

[abstract] [bib] [arxiv]

- Guy Blanc, Neha Gupta, Gregory Valiant, and Paul Valiant,
*Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process.*COLT, 2020.

[abstract] [bib] [pdf]

- Antonio A. Ginart, Melody Y. Guan, Gregory Valiant, and James Zou,
*Making AI Forget You: Data Deletion in Machine Learning*, NeurIPS, 2019.

*[abstract] [bib] [pdf]*

- Vatsal Sharan, Aaron Sidford, and Gregory Valiant,
*Memory-Sample Tradeoffs for Linear Regression with Small Error.*STOC, 2019.

[abstract] [bib] [arxiv]

- Vatsal Sharan, Kai Sheng Tai, Peter Bailis, and Gregory Valiant,
*Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data.*ICML, 2019.

- Kai Sheng Tai, Peter Bailis, and Gregory Valiant,
*Equivariant Transformer Networks.*ICML, 2019.

- Ramya Vinayak, Weihao Kong, Gregory Valiant, and Sham Kakade,
*Maximum Likelihood Estimation for Learning Populations of Parameters.*ICML, 2019 (to appear).

- Mingda Qiao and Gregory Valiant,
*A Theory of Selective Prediction.*COLT, 2019 (to appear).

[abstract] [bib] [arxiv]

- Weihao Kong and Gregory Valiant,
*Estimating Learnability in the Sublinear Data Regime.*NeurIPS, 2018.

[abstract] [bib] [pdf full version][code]

- Shivam Garg, Vatsal Sharan, Brian Hu Zhang, and Gregory Valiant,
*A Spectral View of Adversarially Robust Features.*NeurIPS, 2018.

[abstract] [bib] [pdf]

- Vatsal Sharan, Sham Kakade, Percy Liang, and Gregory Valiant,
*Prediction with a Short Memory.*STOC, 2018.

[abstract] [bib] [pdf]

- Michela Meister and Gregory Valiant,
*A Data Prism: Semi-Verified Learning in the Small-alpha Regime.*COLT, 2018.

[abstract] [bib] [pdf]

- Mingda Qiao and Gregory Valiant,
*Learning Discrete Distributions from Untrusted Batches.*ITCS, 2018.

- Qingqing Huang, Sham M. Kakade, Weihao Kong and Gregory Valiant,
*Recovering Structured Probability Matrices.*ITCS, 2018.

- Jacob Steinhardt, Moses Charikar and Gregory Valiant,
*Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers.*ITCS, 2018.

- Kevin Tian, Weihao Kong, and Gregory Valiant,
*Learning Populations of Parameters.*NIPS, 2017. [pdf]

- Vatsal Sharan, Sham Kakade, Percy Liang, and Gregory Valiant,
*Learning Overcomplete HMMs.*NIPS, 2017.

- W. Kong, G. Valiant,
*Spectrum Estimation from Samples,*Annals of Statistics, 2017.

[abstract] [bib] [pdf][MATLAB Code]

- Vatsal Sharan and Gregory Valiant,
*Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use.*ICML, 2017.

- Aditi Raghunathan, Gregory Valiant and James Zou.
*Estimating the Unseen from Multiple Populations*. ICML, 2017.

- Moses Charikar, Jacob Steinhardt, and Gregory Valiant,
*Learning from Untrusted Data*. STOC, 2017.

[abstract] [bib] [arxiv][pdf]

- Jacob Steinhardt, Gregory Valiant, and Moses Charikar,
*Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction,*NIPS, 2016.

[abstract] [bib] [arxiv]

- James Zou , Greg Valiant, Paul Valiant, Konrad Karczewski, Siu On Chan, Kaitlin Samocha, Monkol Lek, Shamil Sunyaev, Mark Daly, and Daniel MacArthur
*Quantifying the unobserved protein-coding variants in human populations provides a roadmap for large-scale sequencing projects.*Nature Communications (7), 2016.

[pdf]

- J. Steinhardt, G. Valiant, and S. Wager,
*Memory, Communication, and Statistical Queries,*COLT, 2016.

[abstract] [bib] [pdf][eccc]

- Gregory Valiant, and Paul Valiant,
*Instance Optimal Learning of Discrete Distributions,*STOC, 2016.

[abstract] [bib] [pdf][older arXiv version]

- Bhaswar Bhattacharya and Gregory Valiant,
*Testing closeness with unequal sized samples,*NIPS, 2015.

[abstract] [bib] [pdf]

- Gregory Valiant, and Paul Valiant,
*An Automatic Inequality Prover and Instance Optimal Identity Testing,*FOCS, 2014.

[abstract] [bib] [conference version] [full version] [**MATLAB code for automated inequality prover!!!**]

Also see Dick Lipton's extremely nice blog post about this paper here!!

- Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang,
*Learning Polynomials with Neural Networks,*ICML 2014.

[pdf]

- Alekh Agarwal, Sham Kakade, Nikos Karampatziakis, Le Song, and Gregory Valiant,
*Learning Least Squares Revisited: Scalable Approaches for Multi-class Prediction,*ICML 2014.

[pdf]

- Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant,
*Optimal algorithms for testing closeness of discrete distributions*, SODA, 2014.

[abstract] [bib] [arxiv]

- Alexandr Andoni, Rina Panigrahy, Gregory Valiant, and Li Zhang,
*Learning sparse polynomial functions*,

SODA, 2014.

[abstract] [bib] [pdf]

- Gregory Valiant, and Paul Valiant
*Estimating the unseen: improved estimators for entropy and other properties*,

NIPS 2013.

[abstract] [bib] [pdf] [full version]

- Gregory Valiant,
*Finding correlations in subquadratic time, with applications to learning parities and juntas*,

In FOCS 2012, and J.ACM

[abstract] [bib] [pdf (conference)] [JACM full version]

- Costis Daskalakis, Ilias Diakonikolas, Rocco Servedio, Gregory Valiant, and Paul Valiant,
*Testing k-modal distributions: optimal algorithms via reductions*,

In the ACM-SIAM Symposium on Discrete Algorithms, SODA 2013.

- Gregory Valiant, and Paul Valiant,
*The power of linear estimators*, 2011.

In the 52nd Annual IEEE Symposium on the Foundations of Computer Science, FOCS 2011.

[abstract] [bib] [pdf] [full version pdf (in progress)]

- Gregory Valiant, and Paul Valiant,
*Estimating the unseen: a sublinear-sample canonical estimator of distributions*, 2010.

[abstract] [bib] [eccc] [full version]

- Gregory Valiant, and Paul Valiant,
*A CLT and tight lower bounds for estimating entropy*, 2010.

[abstract] [bib] [eccc]

The above two papers appeared together as:

In the 43rd ACM Symposium on Theory of Computing, STOC 2011.

[abstract] [bib] [pdf]

- Adam Kalai, Ankur Moitra, and Gregory Valiant,
*Disentangling Gaussians*,

Communications of the ACM, 55(2). February, 2012.

- Ankur Moitra, and Gregory Valiant,
*Settling the Polynomial Learnability of Mixtures of Gaussians*,

In the 51st Annual IEEE Symposium on the Foundations of Computer Science, FOCS 2010.

Invited to Research Highlights section of the Communications of the ACM.

[abstract] [bib] [arXiv][pdf (conference version)]

(Also see the related paper of Belkin and Sinha, showing that a method of moments applies to a more general class of mixture distributions, though obtaining slightly weaker results in the case of GMMs.)

- Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant,
*Efficiently Learning Mixtures of Two Gaussians*,

In the 42nd ACM Symposium on Theory of Computing, STOC 2010.

[abstract] [bib] [pdf][full version pdf (in progress)]

- Adi Livnat, Christos Papadimitriou, Aviad Rubinstein, Andrew Wan, and Gregory Valiant
*Satisfiability and Evolution,*FOCS, 2014.

[pdf]

- Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant,
*Size and Treewidth Bounds for Conjunctive Queries*,

Journal of the ACM, 2012. [abstract] [pdf(preprint)]

- Gregory Valiant and Paul Valiant,
*Size Bounds for Conjunctive Queries with General Functional Dependencies*,

[abstract] [bib] [arXiv]

- Georg Gottlob, Stephanie Tien Lee, and Gregory Valiant,
*Size and Treewidth Bounds for Conjunctive Queries*,

In the Symposium on Principles of Database Systems, PODS 2009. Best Paper Award. Invited to Journal of the ACM.

[abstract] [bib] [pdf]

- Noam Nisan, Michael Schapira, Gregory Valiant, and Aviv Zohar,
*Best-Response Auctions*,

In the 12th ACM Conference on Electronic Commerce, EC 2011.

[abstract] [bib] [pdf]

- Christos Papadimitriou and Gregory Valiant,
*A New Look at Selfish Routing*,

In Innovations in Computer Science, ICS 2010.

[abstract] [bib] [pdf]

- Noam Nisan, Michael Schapira, Gregory Valiant, and Aviv Zohar,
*Best-Response Mechanisms*,

In the 2nd conference on Innovations in Computer Science, ICS 2011.

[abstract] [bib] [pdf]

- Constantinos Daskalakis, Rafael Frongillo, Christos H. Papadimitriou, George Pierrakos, and Gregory Valiant,
*On Learning Algorithms for Nash Equilibria.*,

In the 3rd International Symposium on Algorithmic Game Theory, SAGT 2010.

[abstract] [bib] [pdf]

- Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant, and Paul Valiant,
*On the Complexity of Nash Equilibria of Action-Graph Games*,

In the 20th ACM-SIAM Symposium on Discrete Algorithms, SODA 2009.

[abstract] [bib] [pdf]

- Ho-Lin Chen, Tim Roughgarden, and Gregory Valiant,
*Designing Network Protocols for Good Equilibria*,

SIAM Journal on Computing, 39(5): 1799-1832, 2010.

Originally appeared as*Designing Networks With Good Equilibria*, in the 19th ACM-SIAM Symposium on Discrete Algorithms, SODA 2008.

[abstract] [bib] [pdf (conference)]

- Gregory Valiant and Tim Roughgarden,
*Braess's Paradox in Large Random Graphs*,

Random Structures and Algorithms, 37(4): 495--515, 2010.

A preliminary version appeared in the 7th ACM Conference on Electronic Commerce, EC 2006.

[abstract] [bib] [pdf (conference)]

During undergrad I did some work in Planetary Science, studying Martian impact craters.

- Sarah Stewart and Gregory Valiant,
*Martian subsurface properties and crater formation processes inferred from fresh impact crater geometries*,

Meteoritics & Planetary Science. 41 (10), 2006

[abstract] [bib] [pdf]