53 citations · 420 across the 50 of their papers we have counts for
16 papers · 1 filter
Efficient Robust Learning at the Information-Theoretic Limit
Adam R. Klivans, Konstantinos Stavropoulos, Sergei Tikhonov +1
In an important recent work, Blanc (2026) gave an algorithm for robustly learning Boolean concept classes with respect to a fixed distribution that outputs a (randomized) classifie…
The Grothendieck Constant is Less Than
Alan Li, Rahul Saha, Anton Xue +4
We prove that the Grothendieck constant . This improves on the work of Braverman, Makarychev, Makarychev, and Naor (2011), who proved…
Iterative Chow Filtering for Learning with Distribution Shift
Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans +2
Recent work due to Goel et al. gave the first efficient algorithms for learning with distribution shift in the challenging PQ framework. In this setting, a learner receives labeled…
Equivalence of Coarse and Fine-Grained Models for Learning with Distribution Shift
Adam R. Klivans, Shyamal Patel, Konstantinos Stavropoulos +1
Recent work on provably efficient algorithms for learning with distribution shift has focused on two models: PQ learning (Goldwasser et al. (2020)) and TDS learning (Klivans et al.…
A Fully Polynomial-Time Algorithm for Robustly Learning Halfspaces over the Hypercube
Gautam Chandrasekaran, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first fully polynomial-time algorithm for learning halfspaces with respect to the uniform distribution on the hypercube in the presence of contamination, where an adver…
Learning Neural Networks with Distribution Shift: Efficiently Certifiable Guarantees
Gautam Chandrasekaran, Adam R. Klivans, Lin Lin Lee +1
We give the first provably efficient algorithms for learning neural networks with distribution shift. We work in the Testable Learning with Distribution Shift framework (TDS learni…
Learning Constant-Depth Circuits in Malicious Noise Models
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
The seminal work of Linial, Mansour, and Nisan gave a quasipolynomial-time algorithm for learning constant-depth circuits () with respect to the uniform distribution…
Efficient Discrepancy Testing for Learning with Distribution Shift
Gautam Chandrasekaran, Adam R. Klivans, Vasilis Kontonis +2
A fundamental notion of distance between train and test distributions from the field of domain adaptation is discrepancy distance. While in general hard to compute, here we provide…
Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
Recent work of Klivans, Stavropoulos, and Vasilyan initiated the study of testable learning with distribution shift (TDS learning), where a learner is given labeled samples from tr…
Testable Learning with Distribution Shift
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
We revisit the fundamental problem of learning with distribution shift, in which a learner is given labeled samples from training distribution , unlabeled samples from test dist…
Learning Mixtures of Gaussians Using the DDPM Objective
Kulin Shah, Sitan Chen, Adam Klivans
Recent works have shown that diffusion models can learn essentially any distribution provided one can perform score estimation. Yet it remains poorly understood under what settings…
The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning
Aravind Gollakota, Sushrut Karmalkar, Adam Klivans
We consider the problem of distribution-free learning for Boolean function classes in the PAC and agnostic models. Generalizing a beautiful work of Malach and Shalev-Shwartz (2022)…
List-Decodable Linear Regression
Sushrut Karmalkar, Adam R. Klivans, Pravesh K. Kothari
We give the first polynomial-time algorithm for robust regression in the list-decodable setting where an adversary can corrupt a greater than fraction of examples. For any $α…
Learning Ising Models with Independent Failures
Surbhi Goel, Daniel M. Kane, Adam R. Klivans
We give the first efficient algorithm for learning the structure of an Ising model that tolerates independent failures; that is, each entry of the observed sample is missing with s…
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time
Surbhi Goel, Adam Klivans
We give a polynomial-time algorithm for learning neural networks with one layer of sigmoids feeding into any Lipschitz, monotone activation function (e.g., sigmoid or ReLU). We mak…
Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs
Parikshit Gopalan, Adam Klivans, Raghu Meka
We give a deterministic, polynomial-time algorithm for approximately counting the number of {0,1}-solutions to any instance of the knapsack problem. On an instance of length n with…