13 citations · 14 across the 19 of their papers we have counts for
5 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…
Proper Agnostic Learning of Functions of Halfspaces under Gaussian Marginals
Sergei Tikhonov, Arsen Vasilyan
We study the problem of computationally efficient proper agnostic learning of multidimensional concept classes under the Gaussian distribution. In this setting, given i.i.d. labele…
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…
Learning Under Graphical Models
Gautam Chandrasekaran, Jason Gaitonde, Ankur Moitra +1
In a landmark result, Linial, Mansour and Nisan (J. ACM 1993) gave a quasipolynomial-time algorithm for learning constant-depth circuits given labeled i.i.d. samples under the unif…
Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension
Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan
Recent work has shown the surprising power of low-degree sandwiching polynomial approximators in the context of challenging learning settings such as learning with distribution shi…