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

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

[pdf]

- James Zou , Greg Valiant, Paul Valiant, Konrad Karczewski, Siu On Chan, Kaitlin Samocha, Monkol Lek, Exome Aggregation Consortium, Shamil Sunyaev, Mark Daly, and Daniel MacArthur
*Quantifying the unobserved protein-coding variants in human populations provides a roadmap for large-scale sequencing projects*under review.

[preprint]

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

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

- Gregory Valiant, and Paul Valiant,
*Instance Optimal Learning,*2015.

[abstract] [bib] [arXiv version]

- 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 the 53rd Annual IEEE Symposium on the Foundations of Computer Science, FOCS 2012.

[abstract] [bib] [pdf (conference)] [pdf (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]

- 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)]

- 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]