13 citations · 13 across the 4 of their papers we have counts for
15 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…
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…
Testable algorithms for approximately counting edges and triangles in sublinear time and space
Talya Eden, Ronitt Rubinfeld, Arsen Vasilyan
We consider the fundamental problems of approximately counting the numbers of edges and triangles in a graph in sublinear time. Previous algorithms for these tasks are significantl…
Robust learning of halfspaces under log-concave marginals
Jane Lange, Arsen Vasilyan
We say that a classifier is \emph{adversarially robust} to perturbations of norm if, with high probability over a point drawn from the input distribution, there is no point…