Publications (31)
Estimating Learnability in the Sublinear Data Regime
Weihao Kong, Gregory Valiant
Size Bounds for Conjunctive Queries with General Functional Dependencies
Gregory Valiant, Paul Valiant
Equivariant Transformer Networks
Kai Sheng Tai, Peter Bailis, Gregory Valiant
Instance Optimal Learning
Gregory Valiant, Paul Valiant
Settling the Polynomial Learnability of Mixtures of Gaussians
Ankur Moitra, Gregory Valiant
Maximum Likelihood Estimation for Learning Populations of Parameters
Ramya Korlakai Vinayak, Weihao Kong, Gregory Valiant +1
An Efficient Algorithm for High-Dimensional Log-Concave Maximum Likelihood
Brian Axelrod, Gregory Valiant
Approximating the Spectrum of a Graph
David Cohen-Steiner, Weihao Kong, Christian Sohler +1
Optimal Algorithms for Testing Closeness of Discrete Distributions
Siu-On Chan, Ilias Diakonikolas, Gregory Valiant +1
Spectrum Estimation from Samples
Weihao Kong, Gregory Valiant
Learning from Untrusted Data
Moses Charikar, Jacob Steinhardt, Gregory Valiant
Avoiding Imposters and Delinquents: Adversarial Crowdsourcing and Peer Prediction
Jacob Steinhardt, Gregory Valiant, Moses Charikar
Testing Closeness With Unequal Sized Samples
Bhaswar B. Bhattacharya, Gregory Valiant
Compressed Factorization: Fast and Accurate Low-Rank Factorization of Compressively-Sensed Data
Vatsal Sharan, Kai Sheng Tai, Peter Bailis +1
Information Theoretically Secure Databases
Gregory Valiant, Paul Valiant
Testing $k$-Modal Distributions: Optimal Algorithms via Reductions
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio +2
Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use
Vatsal Sharan, Gregory Valiant
Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers
Jacob Steinhardt, Moses Charikar, Gregory Valiant
A Theory of Selective Prediction
Mingda Qiao, Gregory Valiant
Recovering Structured Probability Matrices
Qingqing Huang, Sham M. Kakade, Weihao Kong +1
On the Complexity of Nash Equilibria of Action-Graph Games
Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant +1
Learning Discrete Distributions from Untrusted Batches
Mingda Qiao, Gregory Valiant
Learning Overcomplete HMMs
Vatsal Sharan, Sham Kakade, Percy Liang +1
Prediction with a Short Memory
Vatsal Sharan, Sham Kakade, Percy Liang +1
Computation in anonymous networks
Elchanan Mossel, Anupam Prakash, Gregory Valiant
Least Squares Revisited: Scalable Approaches for Multi-class Prediction
Alekh Agarwal, Sham M. Kakade, Nikos Karampatziakis +2
Learning Populations of Parameters
Kevin Tian, Weihao Kong, Gregory Valiant
Satisfiability and Evolution
Adi Livnat, Christos Papadimitriou, Aviad Rubinstein +2
A Polynomial Time Algorithm for Log-Concave Maximum Likelihood via Locally Exponential Families
Brian Axelrod, Ilias Diakonikolas, Anastasios Sidiropoulos +2
A Data Prism: Semi-Verified Learning in the Small-Alpha Regime
Michela Meister, Gregory Valiant
Sketching Linear Classifiers over Data Streams
Kai Sheng Tai, Vatsal Sharan, Peter Bailis +1