Academic Appointments


Professional Education


  • PhD, UC Berkeley, Computer Science (2012)
  • BA, Harvard University, Mathematics (2006)

Current Research and Scholarly Interests


My primary research interests lie at the intersection of algorithms, learning, applied probability, and statistics. I am particularly interested in understanding the algorithmic and information theoretic possibilities and limitations for many fundamental information extraction tasks that underly real-world machine learning and data-centric applications. I am also interested in evolution, and game theory.

All Publications


  • Learning Sparse Polynomial Functions. Andoni, A., Panigrahy, R., Valiant, G., Zhang, L. 2014
  • Optimal Algorithms for Testing Closeness of Discrete Distributions. Chan, S., Diakonikolas, I., Valiant, P., Valiant, G. 2014
  • Computation in anonymous networks. CoRR abs/1306.4151 Mossel, E., Prakash, A., Valiant, G. 2013
  • Instance-by-instance optimal identity testing. Electronic Colloquium on Computational Complexity (ECCC) Valiant, G., Valiant, P. 2013; 20: 111
  • Testing k-Modal Distributions: Optimal Algorithms via Reductions. Daskalakis, C., Diakonikolas, I., Servedio, Rocco, A., Valiant, G., Valiant, P. 2013
  • Optimal Algorithms for Testing Closeness of Discrete Distributions. CoRR abs/1308.3946 Chan, S., Diakonikolas, I., Valiant, G., Valiant, P. 2013
  • Estimating the Unseen: Improved Estimators for Entropy and other Properties. Valiant, P., Valiant, G. 2013
  • Least Squares Revisited: Scalable Approaches for Multi-class Prediction. CoRR abs/1310.1949 Agarwal, A., Kakade, Sham, M., Karampatziakis, N., Song, L., Valiant, G. 2013
  • Size and Treewidth Bounds for Conjunctive Queries. J. ACM Gottlob, G., Lee, S. T., Valiant, G., Valiant, P. 2012; 3 (59): 16
  • Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas. Valiant, G. 2012
  • Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise. Electronic Colloquium on Computational Complexity (ECCC) Valiant, G. 2012; 19: 6
  • Disentangling Gaussians. Commun. ACM Kalai, A. T., Moitra, A., Valiant, G. 2012; 2 (55): 113-120
  • Beating brute-force: Improved algorithms for finding correlations, and related problems. TinyToCS Valiant, G. 2012; 1
  • Testing $k$-Modal Distributions: Optimal Algorithms via Reductions. CoRR abs/1112.5659 Daskalakis, C., Diakonikolas, I., Servedio, Rocco, A., Valiant, G., Valiant, P. 2011
  • The Power of Linear Estimators. Valiant, G., Valiant, P. 2011
  • Best-response auctions. Nisan, N., Schapira, M., Valiant, G., Zohar, A. 2011
  • When is it best to best-respond? SIGecom Exchanges Nisan, N., Schapira, M., Valiant, G., Zohar, A. 2011; 2 (10): 16-18
  • Best-Response Mechanisms. Nisan, N., Schapira, M., Valiant, G., Zohar, A. 2011
  • Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. Valiant, G., Valiant, P. 2011
  • Incentive-compatible distributed greedy protocols. Nisan, N., Schapira, M., Valiant, G., Zohar, A. 2011
  • Braess's Paradox in Large Random Graphs RANDOM STRUCTURES & ALGORITHMS Valiant, G., Roughgarden, T. 2010; 37 (4): 495-515

    View details for DOI 10.1002/rsa.20325

    View details for Web of Science ID 000284038400006

  • DESIGNING NETWORK PROTOCOLS FOR GOOD EQUILIBRIA SIAM JOURNAL ON COMPUTING Chen, H., Roughgarden, T., Valiant, G. 2010; 39 (5): 1799-1832

    View details for DOI 10.1137/08072721X

    View details for Web of Science ID 000277584700005

  • Estimating the unseen: A sublinear-sample canonical estimator of distributions. Electronic Colloquium on Computational Complexity (ECCC) Valiant, G., Valiant, P. 2010; 17: 180
  • Settling the Polynomial Learnability of Mixtures of Gaussians. CoRR abs/1004.4223 Moitra, A., Valiant, G. 2010
  • A New Look at Selfish Routing. Papadimitriou, Christos, H., Valiant, G. 2010
  • Efficiently learning mixtures of two Gaussians. Kalai, A. T., Moitra, A., Valiant, G. 2010
  • Settling the Polynomial Learnability of Mixtures of Gaussians. Moitra, A., Valiant, G. 2010
  • A CLT and tight lower bounds for estimating entropy. Electronic Colloquium on Computational Complexity (ECCC) Valiant, G., Valiant, P. 2010; 17: 183
  • On Learning Algorithms for Nash Equilibria. Daskalakis, C., Frongillo, Rafael, M., Papadimitriou, Christos, H., Pierrakos, G., Valiant, G. 2010
  • Size Bounds for Conjunctive Queries with General Functional Dependencies. CoRR abs/0909.2030 Valiant, G., Valiant, P. 2009
  • On the complexity of Nash equilibria of action-graph games. Daskalakis, C., Schoenebeck, G., Valiant, G., Valiant, P. 2009
  • Size and treewidth bounds for conjunctive queries. Gottlob, G., Lee, S. T., Valiant, G. 2009
  • Designing Networks with Good Equilibria 19th ACM-SIAM Symposium on Discrete Algorithms Chen, H., Roughgarden, T., Valiant, G. SIAM. 2008: 854–863
  • On the Complexity of Nash Equilibria of Action-Graph Games. CoRR abs/0802.1604 Daskalakis, C., Schoenebeck, G., Valiant, G., Valiant, P. 2008
  • Braess's paradox in large random graphs. Valiant, G., Roughgarden, T. 2006