Academic Appointments

Professional Education

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

Contact

  • gvaliant@stanford.edu
    University - Faculty Department: Computer Science Position: Asst Professor

Additional Info

  • Mail Code: 9045

Links

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.

2018-19 Courses

Stanford Advisees

All Publications

  • Learning from Untrusted Data Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) Charikar, M., Steinhardt, J., Valiant, G.
  • SPECTRUM ESTIMATION FROM SAMPLES ANNALS OF STATISTICS Kong, W., Valiant, G. 2017; 45 (5): 2218–47

    View details for DOI 10.1214/16-AOS1525

    View details for Web of Science ID 000416455300014

  • AN AUTOMATIC INEQUALITY PROVER AND INSTANCE OPTIMAL IDENTITY TESTING SIAM JOURNAL ON COMPUTING Valiant, G., Valiant, P. 2017; 46 (1): 429-455

    View details for DOI 10.1137/151002526

    View details for Web of Science ID 000396677400016

  • Quantifying unobserved protein-coding variants in human populations provides a roadmap for large-scale sequencing projects. Nature communications Zou, J., Valiant, G., Valiant, P., Karczewski, K., Chan, S. O., Samocha, K., Lek, M., Sunyaev, S., Daly, M., MacArthur, D. G. 2016; 7: 13293-?

    Abstract

    As new proposals aim to sequence ever larger collection of humans, it is critical to have a quantitative framework to evaluate the statistical power of these projects. We developed a new algorithm, UnseenEst, and applied it to the exomes of 60,706 individuals to estimate the frequency distribution of all protein-coding variants, including rare variants that have not been observed yet in the current cohorts. Our results quantified the number of new variants that we expect to identify as sequencing cohorts reach hundreds of thousands of individuals. With 500K individuals, we find that we expect to capture 7.5% of all possible loss-of-function variants and 12% of all possible missense variants. We also estimate that 2,900 genes have loss-of-function frequency of <0.00001 in healthy humans, consistent with very strong intolerance to gene inactivation.

    View details for DOI 10.1038/ncomms13293

    View details for PubMedID 27796292

    View details for PubMedCentralID PMC5095512

  • Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem JOURNAL OF THE ACM Valiant, G. 2015; 62 (2)

    View details for DOI 10.1145/2728167

    View details for Web of Science ID 000354799200004

  • 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
  • Best-Response Mechanisms. Nisan, N., Schapira, M., Valiant, G., Zohar, A. 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
  • 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

  • Efficiently learning mixtures of two Gaussians. Kalai, A. T., Moitra, A., Valiant, G. 2010
  • A New Look at Selfish Routing. Papadimitriou, Christos, H., Valiant, G. 2010
  • 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
  • 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

    View details for Web of Science ID 000281596900094

  • 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