default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDGregory Valiant
Person information
- affiliation: University of California, Berkeley, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c68]Gregory Valiant:
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis. ITCS 2024: 96:1-96:13- [c67]Spencer Compton
, Gregory Valiant:
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances. STOC 2024: 194-200 - [i63]Guy Blanc, Gregory Valiant:
Adaptive and oblivious statistical adversaries are equivalent. CoRR abs/2410.13548 (2024) - 2023
- [c66]Steven Cao, Percy Liang, Gregory Valiant:
One-sided Matrix Completion from Two Observations Per Row. ICML 2023: 3599-3624 - [c65]Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant:
Efficient Convex Optimization Requires Superlinear Memory (Extended Abstract). IJCAI 2023: 6468-6473 - [c64]Mingda Qiao, Gregory Valiant:
Online Pen Testing. ITCS 2023: 91:1-91:26 - [c63]Qian Huang, Eric Zelikman, Sarah Chen, Yuhuai Wu, Gregory Valiant, Percy Liang:
Lexinvariant Language Models. NeurIPS 2023 - [i62]Qian Huang, Eric Zelikman, Sarah Li Chen, Yuhuai Wu, Gregory Valiant, Percy Liang:
Lexinvariant Language Models. CoRR abs/2305.16349 (2023) - [i61]Steven Cao, Percy Liang, Gregory Valiant:
One-sided Matrix Completion from Two Observations Per Row. CoRR abs/2306.04049 (2023) - [i60]Shivam Garg, Chirag Pabbaraju, Kirankumar Shiragur, Gregory Valiant:
Testing with Non-identically Distributed Samples. CoRR abs/2311.11194 (2023) - [i59]Gregory Valiant:
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis. CoRR abs/2311.16342 (2023) - [i58]Spencer Compton, Gregory Valiant:
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances. CoRR abs/2312.02417 (2023) - 2022
- [c62]Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant:
Efficient Convex Optimization Requires Superlinear Memory. COLT 2022: 2390-2430 - [c61]Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan:
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. COLT 2022: 2431-2540 - [c60]Shivam Garg, Dimitris Tsipras, Percy Liang, Gregory Valiant:
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes. NeurIPS 2022 - [i57]Brian Axelrod, Shivam Garg, Yanjun Han, Vatsal Sharan, Gregory Valiant:
On the Statistical Complexity of Sample Amplification. CoRR abs/2201.04315 (2022) - [i56]Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant:
Efficient Convex Optimization Requires Superlinear Memory. CoRR abs/2203.15260 (2022) - [i55]Theo Jepsen, Stephen Ibanez, Gregory Valiant, Nick McKeown:
From Sand to Flour: The Next Leap in Granular Computing with NanoSort. CoRR abs/2204.12615 (2022) - [i54]Shivam Garg, Dimitris Tsipras, Percy Liang, Gregory Valiant:
What Can Transformers Learn In-Context? A Case Study of Simple Function Classes. CoRR abs/2208.01066 (2022) - [i53]Mingda Qiao, Gregory Valiant:
Online Pen Testing. CoRR abs/2210.00655 (2022) - 2021
- [c59]Kartik Chandra, Chuma Kabaghe, Gregory Valiant:
Beyond Laurel/Yanny: An Autoencoder-Enabled Search for Polyperceivable Audio. ACL/IJCNLP (2) 2021: 593-598 - [c58]Annie Marsden, John C. Duchi, Gregory Valiant:
Misspecification in Prediction Problems and Robustness via Improper Learning. AISTATS 2021: 2161-2169 - [c57]Mingda Qiao, Gregory Valiant:
Exponential Weights Algorithms for Selective Learning. COLT 2021: 3833-3858 - [c56]Kai Sheng Tai, Peter Bailis, Gregory Valiant:
Sinkhorn Label Allocation: Semi-Supervised Classification via Annealed Self-Training. ICML 2021: 10065-10075 - [c55]Mingda Qiao, Gregory Valiant:
Stronger calibration lower bounds via sidestepping. STOC 2021: 456-466 - [i52]Annie Marsden, John C. Duchi, Gregory Valiant:
On Misspecification in Prediction Problems and Robustness via Improper Learning. CoRR abs/2101.05234 (2021) - [i51]Kai Sheng Tai, Peter Bailis, Gregory Valiant:
Sinkhorn Label Allocation: Semi-Supervised Classification via Annealed Self-Training. CoRR abs/2102.08622 (2021) - [i50]Mingda Qiao, Gregory Valiant:
Exponential Weights Algorithms for Selective Learning. CoRR abs/2106.15662 (2021) - [i49]Jonathan A. Kelner, Annie Marsden, Vatsal Sharan, Aaron Sidford, Gregory Valiant, Honglin Yuan:
Big-Step-Little-Step: Efficient Gradient Methods for Objectives with Multiple Scales. CoRR abs/2111.03137 (2021) - 2020
- [c54]Weihao Kong, Emma Brunskill, Gregory Valiant:
Sublinear Optimal Policy Value Estimation in Contextual Bandits. AISTATS 2020: 4377-4387 - [c53]Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant:
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process. COLT 2020: 483-513 - [c52]Brian Axelrod, Shivam Garg, Vatsal Sharan, Gregory Valiant:
Sample Amplification: Increasing Dataset Size even when Learning is Impossible. ICML 2020: 442-451 - [c51]Sen Wu, Hongyang R. Zhang, Gregory Valiant, Christopher Ré:
On the Generalization Effects of Linear Transformations in Data Augmentation. ICML 2020: 10410-10420 - [c50]Justin Y. Chen, Gregory Valiant, Paul Valiant:
Worst-Case Analysis for Randomly Collected Data. NeurIPS 2020 - [p1]Gregory Valiant, Paul Valiant:
Instance Optimal Distribution Testing and Learning. Beyond the Worst-Case Analysis of Algorithms 2020: 506-526 - [i48]Sen Wu, Hongyang R. Zhang, Gregory Valiant, Christopher Ré:
On the Generalization Effects of Linear Transformations in Data Augmentation. CoRR abs/2005.00695 (2020) - [i47]Mingda Qiao, Gregory Valiant:
Stronger Calibration Lower Bounds via Sidestepping. CoRR abs/2012.03454 (2020)
2010 – 2019
- 2019
- [c49]Melody Y. Guan, Gregory Valiant:
A Surprising Density of Illusionable Natural Speech. CogSci 2019: 1871 - [c48]Mingda Qiao, Gregory Valiant:
A Theory of Selective Prediction. COLT 2019: 2580-2594 - [c47]Vatsal Sharan, Kai Sheng Tai, Peter Bailis, Gregory Valiant:
Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data. ICML 2019: 5690-5700 - [c46]Kai Sheng Tai, Peter Bailis, Gregory Valiant:
Equivariant Transformer Networks. ICML 2019: 6086-6095 - [c45]Ramya Korlakai Vinayak, Weihao Kong, Gregory Valiant, Sham M. Kakade:
Maximum Likelihood Estimation for Learning Populations of Parameters. ICML 2019: 6448-6457 - [c44]Antonio Ginart, Melody Y. Guan, Gregory Valiant, James Zou:
Making AI Forget You: Data Deletion in Machine Learning. NeurIPS 2019: 3513-3526 - [c43]Brian Axelrod, Ilias Diakonikolas, Alistair Stewart, Anastasios Sidiropoulos, Gregory Valiant:
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families. NeurIPS 2019: 7721-7733 - [c42]Vatsal Sharan, Aaron Sidford, Gregory Valiant:
Memory-sample tradeoffs for linear regression with small error. STOC 2019: 890-901 - [i46]Kai Sheng Tai, Peter Bailis, Gregory Valiant:
Equivariant Transformer Networks. CoRR abs/1901.11399 (2019) - [i45]Mingda Qiao, Gregory Valiant:
A Theory of Selective Prediction. CoRR abs/1902.04256 (2019) - [i44]Ramya Korlakai Vinayak, Weihao Kong, Gregory Valiant, Sham M. Kakade:
Maximum Likelihood Estimation for Learning Populations of Parameters. CoRR abs/1902.04553 (2019) - [i43]Vatsal Sharan, Aaron Sidford, Gregory Valiant:
Memory-Sample Tradeoffs for Linear Regression with Small Error. CoRR abs/1904.08544 (2019) - [i42]Guy Blanc, Neha Gupta, Gregory Valiant, Paul Valiant:
Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like process. CoRR abs/1904.09080 (2019) - [i41]Brian Axelrod, Shivam Garg, Vatsal Sharan, Gregory Valiant:
Sample Amplification: Increasing Dataset Size even when Learning is Impossible. CoRR abs/1904.12053 (2019) - [i40]Melody Y. Guan, Gregory Valiant:
A Surprising Density of Illusionable Natural Speech. CoRR abs/1906.01040 (2019) - [i39]Antonio Ginart, Melody Y. Guan, Gregory Valiant, James Zou:
Making AI Forget You: Data Deletion in Machine Learning. CoRR abs/1907.05012 (2019) - [i38]Brian Axelrod, Ilias Diakonikolas, Anastasios Sidiropoulos, Alistair Stewart, Gregory Valiant:
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families. CoRR abs/1907.08306 (2019) - [i37]Justin Y. Chen, Gregory Valiant, Paul Valiant:
How bad is worst-case data if you know where it comes from? CoRR abs/1911.03605 (2019) - [i36]Weihao Kong, Gregory Valiant, Emma Brunskill:
Sublinear Optimal Policy Value Estimation in Contextual Bandits. CoRR abs/1912.06111 (2019) - 2018
- [c41]Michela Meister, Gregory Valiant:
A Data Prism: Semi-verified learning in the small-alpha regime. COLT 2018: 1530-1546 - [c40]Jacob Steinhardt, Moses Charikar, Gregory Valiant:
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. ITCS 2018: 45:1-45:21 - [c39]Qingqing Huang, Sham M. Kakade, Weihao Kong, Gregory Valiant:
Recovering Structured Probability Matrices. ITCS 2018: 46:1-46:14 - [c38]Mingda Qiao, Gregory Valiant:
Learning Discrete Distributions from Untrusted Batches. ITCS 2018: 47:1-47:20 - [c37]David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant:
Approximating the Spectrum of a Graph. KDD 2018: 1263-1271 - [c36]Weihao Kong, Gregory Valiant:
Estimating Learnability in the Sublinear Data Regime. NeurIPS 2018: 5460-5469 - [c35]Shivam Garg, Vatsal Sharan, Brian Hu Zhang, Gregory Valiant:
A Spectral View of Adversarially Robust Features. NeurIPS 2018: 10159-10169 - [c34]Kai Sheng Tai, Vatsal Sharan, Peter Bailis, Gregory Valiant:
Sketching Linear Classifiers over Data Streams. SIGMOD Conference 2018: 757-772 - [c33]Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant:
Prediction with a short memory. STOC 2018: 1074-1087 - [i35]Weihao Kong, Gregory Valiant:
Estimating Learnability in the Sublinear Data Regime. CoRR abs/1805.01626 (2018) - [i34]Brian Axelrod, Gregory Valiant:
An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood. CoRR abs/1811.03204 (2018) - [i33]Shivam Garg, Vatsal Sharan, Brian Hu Zhang, Gregory Valiant:
A Spectral View of Adversarially Robust Features. CoRR abs/1811.06609 (2018) - 2017
- [j8]Gregory Valiant, Paul Valiant:
Estimating the Unseen: Improved Estimators for Entropy and Other Properties. J. ACM 64(6): 37:1-37:41 (2017) - [j7]Gregory Valiant, Paul Valiant:
An Automatic Inequality Prover and Instance Optimal Identity Testing. SIAM J. Comput. 46(1): 429-455 (2017) - [c32]Aditi Raghunathan, Gregory Valiant, James Zou:
Estimating the unseen from multiple populations. ICML 2017: 2855-2863 - [c31]Vatsal Sharan, Gregory Valiant:
Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use. ICML 2017: 3095-3104 - [c30]Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant:
Learning Overcomplete HMMs. NIPS 2017: 940-949 - [c29]Kevin Tian, Weihao Kong, Gregory Valiant:
Learning Populations of Parameters. NIPS 2017: 5778-5787 - [c28]Moses Charikar, Jacob Steinhardt, Gregory Valiant:
Learning from untrusted data. STOC 2017: 47-60 - [i32]Vatsal Sharan, Gregory Valiant:
Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use. CoRR abs/1703.01804 (2017) - [i31]Jacob Steinhardt, Moses Charikar, Gregory Valiant:
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers. CoRR abs/1703.04940 (2017) - [i30]Vatsal Sharan, Kai Sheng Tai, Peter Bailis, Gregory Valiant:
There and Back Again: A General Approach to Learning Sparse Models. CoRR abs/1706.08146 (2017) - [i29]Aditi Raghunathan, Gregory Valiant, James Zou:
Estimating the unseen from multiple populations. CoRR abs/1707.03854 (2017) - [i28]Michela Meister, Gregory Valiant:
A Data Prism: Semi-Verified Learning in the Small-Alpha Regime. CoRR abs/1708.02740 (2017) - [i27]Kevin Tian, Weihao Kong, Gregory Valiant:
Optimally Learning Populations of Parameters. CoRR abs/1709.02707 (2017) - [i26]Kai Sheng Tai, Vatsal Sharan, Peter Bailis, Gregory Valiant:
Finding Heavily-Weighted Features in Data Streams. CoRR abs/1711.02305 (2017) - [i25]Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant:
Learning Overcomplete HMMs. CoRR abs/1711.02309 (2017) - [i24]Mingda Qiao, Gregory Valiant:
Learning Discrete Distributions from Untrusted Batches. CoRR abs/1711.08113 (2017) - [i23]David Cohen-Steiner, Weihao Kong, Christian Sohler, Gregory Valiant:
Approximating the Spectrum of a Graph. CoRR abs/1712.01725 (2017) - 2016
- [c27]Jacob Steinhardt, Gregory Valiant, Stefan Wager:
Memory, Communication, and Statistical Queries. COLT 2016: 1490-1516 - [c26]Michael S. Crouch, Andrew McGregor, Gregory Valiant, David P. Woodruff:
Stochastic Streams: Sample Complexity vs. Space Complexity. ESA 2016: 32:1-32:15 - [c25]Jacob Steinhardt, Gregory Valiant, Moses Charikar:
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction. NIPS 2016: 4439-4447 - [c24]Gregory Valiant, Paul Valiant:
Instance optimal learning of discrete distributions. STOC 2016: 142-155 - [i22]Weihao Kong, Gregory Valiant:
Spectrum Estimation from Samples. CoRR abs/1602.00061 (2016) - [i21]Qingqing Huang, Sham M. Kakade, Weihao Kong, Gregory Valiant:
Recovering Structured Probability Matrices. CoRR abs/1602.06586 (2016) - [i20]Gregory Valiant, Paul Valiant:
Information Theoretically Secure Databases. CoRR abs/1605.02646 (2016) - [i19]Jacob Steinhardt, Gregory Valiant, Moses Charikar:
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction. CoRR abs/1606.05374 (2016) - [i18]Moses Charikar, Jacob Steinhardt, Gregory Valiant:
Learning from Untrusted Data. CoRR abs/1611.02315 (2016) - [i17]Sham M. Kakade, Percy Liang, Vatsal Sharan, Gregory Valiant:
Prediction with a Short Memory. CoRR abs/1612.02526 (2016) - [i16]Gregory Valiant, Paul Valiant:
Information Theoretically Secure Databases. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j6]Gregory Valiant:
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem. J. ACM 62(2): 13:1-13:45 (2015) - [c23]Bhaswar B. Bhattacharya, Gregory Valiant:
Testing Closeness With Unequal Sized Samples. NIPS 2015: 2611-2619 - [i15]Bhaswar B. Bhattacharya, Gregory Valiant:
Testing Closeness With Unequal Sized Samples. CoRR abs/1504.04599 (2015) - [i14]Gregory Valiant, Paul Valiant:
Instance Optimal Learning. CoRR abs/1504.05321 (2015) - [i13]Jacob Steinhardt, Gregory Valiant, Stefan Wager:
Memory, Communication, and Statistical Queries. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c22]Gregory Valiant, Paul Valiant:
An Automatic Inequality Prover and Instance Optimal Identity Testing. FOCS 2014: 51-60 - [c21]Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan:
Satisfiability and Evolution. FOCS 2014: 524-530 - [c20]Alekh Agarwal, Sham M. Kakade, Nikos Karampatziakis, Le Song, Gregory Valiant:
Least Squares Revisited: Scalable Approaches for Multi-class Prediction. ICML 2014: 541-549 - [c19]Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang:
Learning Polynomials with Neural Networks. ICML 2014: 1908-1916 - [c18]Alexandr Andoni, Rina Panigrahy, Gregory Valiant, Li Zhang:
Learning Sparse Polynomial Functions. SODA 2014: 500-510 - [c17]Siu On Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant:
Optimal Algorithms for Testing Closeness of Discrete Distributions. SODA 2014: 1193-1203 - 2013
- [c16]Paul Valiant, Gregory Valiant:
Estimating the Unseen: Improved Estimators for Entropy and other Properties. NIPS 2013: 2157-2165 - [c15]Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio, Gregory Valiant, Paul Valiant:
Testing k-Modal Distributions: Optimal Algorithms via Reductions. SODA 2013: 1833-1852 - [i12]Elchanan Mossel, Anupam Prakash, Gregory Valiant:
Computation in anonymous networks. CoRR abs/1306.4151 (2013) - [i11]Siu On Chan, Ilias Diakonikolas, Gregory Valiant, Paul Valiant:
Optimal Algorithms for Testing Closeness of Discrete Distributions. CoRR abs/1308.3946 (2013) - [i10]Alekh Agarwal, Sham M. Kakade, Nikos Karampatziakis, Le Song, Gregory Valiant:
Least Squares Revisited: Scalable Approaches for Multi-class Prediction. CoRR abs/1310.1949 (2013) - [i9]Gregory Valiant, Paul Valiant:
Instance-by-instance optimal identity testing. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [b1]Gregory Valiant:
Algorithmic Approaches to Statistical Questions. University of California, Berkeley, USA, 2012 - [j5]Adam Tauman Kalai, Ankur Moitra, Gregory Valiant:
Disentangling Gaussians. Commun. ACM 55(2): 113-120 (2012) - [j4]Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, Paul Valiant:
Size and Treewidth Bounds for Conjunctive Queries. J. ACM 59(3): 16:1-16:35 (2012) - [c14]Gregory Valiant:
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas. FOCS 2012: 11-20 - [i8]Gregory Valiant:
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise. Electron. Colloquium Comput. Complex. TR12 (2012) - [i7]Gregory Valiant:
Beating brute-force: Improved algorithms for finding correlations, and related problems. Tiny Trans. Comput. Sci. 1 (2012) - 2011
- [j3]Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar:
When is it best to best-respond? SIGecom Exch. 10(2): 16-18 (2011) - [c13]Gregory Valiant, Paul Valiant:
The Power of Linear Estimators. FOCS 2011: 403-412 - [c12]Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar:
Best-Response Mechanisms. ICS 2011: 155-165 - [c11]Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar:
Incentive-compatible distributed greedy protocols. PODC 2011: 335-336 - [c10]Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar:
Best-response auctions. EC 2011: 351-360 - [c9]Gregory Valiant, Paul Valiant:
Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. STOC 2011: 685-694 - [i6]Constantinos Daskalakis,