Academic Appointments

Honors & Awards

  • Young Investigator Award, Office of Naval Research (2018)
  • Hellman Faculty Scholar, The Hellman Fellows Program (2017)
  • Sloan Foundation Fellowship, The Sloan Foundation (2016)
  • NSF CAREER Award, National Science Foundation (2014)
  • ACM Doctoral Dissertation Award, Honorable Mention, Association for Computing Machinery (ACM) (2012)

Professional Education

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

Contact

  • Academic
    gvaliant@stanford.edu
    University - Faculty Department: Computer Science Position: Assoc 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.

2025-26 Courses

Stanford Advisees

All Publications

  • Memory-Sample Tradeoffs for Linear Regression with Small Error Symposium on Theory of Computing (STOC) Sharan, V., Sidford, A., Valiant, G. 2019
  • Estimating the Unseen: Improved Estimators for Entropy and Other Properties JOURNAL OF THE ACM Valiant, G., Valiant, P. 2017; 64 (6)

    View details for DOI 10.1145/3125643

    View details for Web of Science ID 000418048800001

  • 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 from Untrusted Data Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) Charikar, M., Steinhardt, J., Valiant, G. 2017
  • Adaptive and Oblivious Statistical Adversaries Are Equivalent Blanc, G., Valiant, G. edited by Koucky, M., Bansal, N. ASSOC COMPUTING MACHINERY. 2025: 2031-2042

    View details for DOI 10.1145/3717823.3718193

    View details for Web of Science ID 001595410700188

  • Generalized Trace Reconstruction Problem: Recovering a String of Probabilities Rivkin, J., Valiant, G., Valiant, P. edited by Koucky, M., Bansal, N. ASSOC COMPUTING MACHINERY. 2025: 1657-1667

    View details for DOI 10.1145/3717823.3718315

    View details for Web of Science ID 001595410700154

  • ON THE STATISTICAL COMPLEXITY OF SAMPLE AMPLIFICATION ANNALS OF STATISTICS Axelrod, B., Garg, S., Han, Y., Sharan, V., Valiant, G. 2024; 52 (6): 2767-2790

    View details for DOI 10.1214/24-AOS2444

    View details for Web of Science ID 001381606500012

  • Efficient Convex Optimization Requires Superlinear Memory JOURNAL OF THE ACM Marsden, A., Sharan, V., Sidford, A., Valiant, G. 2024; 71 (6)

    View details for DOI 10.1145/3689208

    View details for Web of Science ID 001391326700006

  • Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances Compton, S., Valiant, G. edited by Mohar, B., Shinkar, O'Donnell, R. ASSOC COMPUTING MACHINERY. 2024: 194-200

    View details for DOI 10.1145/3618260.3649754

    View details for Web of Science ID 001254099900020

  • Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis Valiant, G. edited by Guruswami SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS. 2024

    View details for DOI 10.4230/LIPIcs.ITCS.2024.96

    View details for Web of Science ID 001300389400096

  • Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract) Marsden, A., Sharan, V., Sidford, A., Valiant, G. edited by Elkind, E. IJCAI-INT JOINT CONF ARTIF INTELL. 2023: 6468-6473

    View details for Web of Science ID 001202344206068

  • Lexinvariant Language Models Huang, Q., Zelikman, E., Li Chen, S., Wu, Y., Valiant, G., Liang, P. edited by Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., Levine, S. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2023

    View details for Web of Science ID 001226352804003

  • One-sided Matrix Completion from Two Observations Per Row Cao, S., Liang, P., Valiant, G. edited by Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, S., Scarlett, J. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2023

    View details for Web of Science ID 001206894303027

  • ReporterSeq reveals genome-wide dynamic modulators of the heat shock response across diverse stressors. eLife Alford, B. D., Tassoni-Tsuchida, E., Khan, D., Work, J. J., Valiant, G., Brandman, O. 2021; 10

    Abstract

    Understanding cellular stress response pathways is challenging because of the complexity of regulatory mechanisms and response dynamics, which can vary with both time and the type of stress. We developed a reverse genetic method called ReporterSeq to comprehensively identify genes regulating a stress-induced transcription factor under multiple conditions in a time-resolved manner. ReporterSeq links RNA-encoded barcode levels to pathway-specific output under genetic perturbations, allowing pooled pathway activity measurements via DNA sequencing alone and without cell enrichment or single-cell isolation. We used ReporterSeq to identify regulators of the heat shock response (HSR), a conserved, poorly understood transcriptional program that protects cells from proteotoxicity and is misregulated in disease. Genome-wide HSR regulation in budding yeast was assessed across 15 stress conditions, uncovering novel stress-specific, time-specific, and constitutive regulators. ReporterSeq can assess the genetic regulators of any transcriptional pathway with the scale of pooled genetic screens and the precision of pathway-specific readouts.

    View details for DOI 10.7554/eLife.57376

    View details for PubMedID 34223816

  • Misspecification in Prediction Problems and Robustness via Improper Learning Marsden, A., Duchi, J., Valiant, G. edited by Banerjee, A., Fukumizu, K. MICROTOME PUBLISHING. 2021

    View details for Web of Science ID 000659893802060

  • Stronger Calibration Lower Bounds via Sidestepping Qiao, M., Valiant, G. edited by Khuller, S., Williams, V. V. ASSOC COMPUTING MACHINERY. 2021: 456-466

    View details for DOI 10.1145/3406325.3451050

    View details for Web of Science ID 000810492500048

  • Sinkhorn Label Allocation: Semi-Supervised Classification via Annealed Self-Training Tai, K., Bailis, P., Valiant, G. edited by Meila, M., Zhang, T. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2021: 7067-7079

    View details for Web of Science ID 000768182700007

  • Beyond Laurel/Yanny: An Autoencoder-Enabled Search for Polyperceivable Audio Chandra, K., Kabaghe, C., Valiant, G., Assoc Computat Linguist ASSOC COMPUTATIONAL LINGUISTICS-ACL. 2021: 593-598

    View details for Web of Science ID 000694699200075

  • Sample Amplification: Increasing Dataset Size even when Learning is Impossible Axelrod, B., Garg, S., Sharan, V., Valiant, G. edited by Daume, H., Singh, A. JMLR-JOURNAL MACHINE LEARNING RESEARCH. 2020

    View details for Web of Science ID 000683178500042

  • A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families Axelrod, B., Diakonikolas, I., Sidiropoulos, A., Stewart, A., Valiant, G. edited by Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019

    View details for Web of Science ID 000534424307071

  • Memory-Sample Tradeoffs for Linear Regression with Small Error Sharan, V., Sidford, A., Valiant, G. edited by Charikar, M., Cohen, E. ASSOC COMPUTING MACHINERY. 2019: 890–901

    View details for DOI 10.1145/3313276.3316403

    View details for Web of Science ID 000523199100080

  • Maximum Likelihood Estimation for Learning Populations of Parameters ICML Vinayak, R., Kong, W., Valiant, G., Kakade, S. 2019
  • Making AI Forget You: Data Deletion in Machine Learning Ginart, A. A., Guan, M. Y., Valiant, G., Zou, J. edited by Wallach, H., Larochelle, H., Beygelzimer, A., d'Alche-Buc, F., Fox, E., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2019

    View details for Web of Science ID 000534424303050

  • A Spectral View of Adversarially Robust Features Garg, S., Sharan, V., Zhang, B., Valiant, G. edited by Bengio, S., Wallach, H., Larochelle, H., Grauman, K., CesaBianchi, N., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018

    View details for Web of Science ID 000461852004067

  • Approximating the Spectrum of a Graph Cohen-Steiner, D., Kong, W., Sohler, C., Valiant, G., ACM ASSOC COMPUTING MACHINERY. 2018: 1263–71

    View details for DOI 10.1145/3219819.3220119

    View details for Web of Science ID 000455346400131

  • Prediction with a Short Memory Sharan, V., Kakade, S., Liang, P., Valiant, G. edited by Diakonikolas, Kempe, D., Henzinger, M. ASSOC COMPUTING MACHINERY. 2018: 1074–87

    View details for DOI 10.1145/3188745.3188954

    View details for Web of Science ID 000458175600092

  • Estimating Learnability in the Sublinear Data Regime Kong, W., Valiant, G. edited by Bengio, S., Wallach, H., Larochelle, H., Grauman, K., CesaBianchi, N., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2018

    View details for Web of Science ID 000461823305047

  • Sketching Linear Classifiers over Data Streams Tai, K., Sharan, V., Bailis, P., Valiant, G. edited by Das, G., Jermaine, C., Bernstein, P., Eldawy, A. ASSOC COMPUTING MACHINERY. 2018: 757–72

    View details for DOI 10.1145/3183713.3196930

    View details for Web of Science ID 000460373700052

  • Learning from Untrusted Data Charikar, M., Steinhardt, J., Valiant, G. edited by Hatami, H., McKenzie, P., King ASSOC COMPUTING MACHINERY. 2017: 47–60

    View details for DOI 10.1145/3055399.3055491

    View details for Web of Science ID 000440317600012

  • Learning Populations of Parameters Tian, K., Kong, W., Valiant, G. edited by Guyon, Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2017

    View details for Web of Science ID 000452649405083

  • Learning Overcomplete HMMs Sharan, V., Kakade, S., Liang, P., Valiant, G. edited by Guyon, Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. NEURAL INFORMATION PROCESSING SYSTEMS (NIPS). 2017

    View details for Web of Science ID 000452649400090

  • 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