Gregory Valiant

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
• Maximum Likelihood Estimation for Learning Populations of Parameters ICML Vinayak, R., Kong, W., Valiant, G., Kakade, S. 2019
• 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

• A Spectral View of Adversarially Robust Features Garg, S., Sharan, V., Zhang, B., Valiant, G., 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

• Learning Overcomplete HMMs Sharan, V., Kakade, S., Liang, P., Valiant, G., 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
• Optimal Algorithms for Testing Closeness of Discrete Distributions. CoRR abs/1308.3946 Chan, S., Diakonikolas, I., Valiant, G., Valiant, P. 2013
• Instance-by-instance optimal identity testing. Electronic Colloquium on Computational Complexity (ECCC) Valiant, G., Valiant, P. 2013; 20: 111
• Computation in anonymous networks. CoRR abs/1306.4151 Mossel, E., Prakash, A., Valiant, G. 2013
• Testing k-Modal Distributions: Optimal Algorithms via Reductions. Daskalakis, C., Diakonikolas, I., Servedio, Rocco, A., 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
• Disentangling Gaussians. Commun. ACM Kalai, A. T., Moitra, A., Valiant, G. 2012; 2 (55): 113-120
• Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas. Valiant, G. 2012
• Beating brute-force: Improved algorithms for finding correlations, and related problems. TinyToCS Valiant, G. 2012; 1
• 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 with Noise. Electronic Colloquium on Computational Complexity (ECCC) Valiant, G. 2012; 19: 6
• 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
• 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
• Testing $k$-Modal Distributions: Optimal Algorithms via Reductions. CoRR abs/1112.5659 Daskalakis, C., Diakonikolas, I., Servedio, Rocco, A., Valiant, G., Valiant, P. 2011
• When is it best to best-respond? SIGecom Exchanges Nisan, N., Schapira, M., Valiant, G., Zohar, A. 2011; 2 (10): 16-18
• 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

• Settling the Polynomial Learnability of Mixtures of Gaussians. Moitra, A., Valiant, G. 2010
• Efficiently learning mixtures of two Gaussians. Kalai, A. T., Moitra, A., Valiant, G. 2010
• On Learning Algorithms for Nash Equilibria. Daskalakis, C., Frongillo, Rafael, M., Papadimitriou, Christos, H., Pierrakos, G., 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
• A CLT and tight lower bounds for estimating entropy. Electronic Colloquium on Computational Complexity (ECCC) Valiant, G., Valiant, P. 2010; 17: 183
• Size Bounds for Conjunctive Queries with General Functional Dependencies. CoRR abs/0909.2030 Valiant, G., Valiant, P. 2009
• Size and treewidth bounds for conjunctive queries. Gottlob, G., Lee, S. T., Valiant, G. 2009
• On the complexity of Nash equilibria of action-graph games. Daskalakis, C., Schoenebeck, G., Valiant, G., Valiant, P. 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