13 citations · 14 across the 19 of their papers we have counts for
24 papers
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…
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…
The Power of Iterative Filtering for Supervised Learning with (Heavy) Contamination
Adam R. Klivans, Konstantinos Stavropoulos, Kevin Tian +1
Inspired by recent work on learning with distribution shift, we give a general outlier removal algorithm called iterative polynomial filtering and show a number of striking applica…
Testing Noise Assumptions of Learning Algorithms
Surbhi Goel, Adam R. Klivans, Konstantinos Stavropoulos +1
We pose a fundamental question in computational learning theory: can we efficiently test whether a training set satisfies the assumptions of a given noise model? This question has…
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…
Plant-and-Steal: Truthful Fair Allocations via Predictions
Ilan Reuven Cohen, Alon Eden, Talya Eden +1
We study truthful mechanisms for approximating the Maximin-Share (MMS) allocation of agents with additive valuations for indivisible goods. Algorithmically, constant factor approxi…
Tolerant Algorithms for Learning with Arbitrary Covariate Shift
Surbhi Goel, Abhishek Shetty, Konstantinos Stavropoulos +1
We study the problem of learning under arbitrary distribution shift, where the learner is trained on a labeled set from one distribution but evaluated on a different, potentially a…
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…
Local Lipschitz Filters for Bounded-Range Functions with Applications to Arbitrary Real-Valued Functions
Jane Lange, Ephraim Linder, Sofya Raskhodnikova +1
We study local filters for the Lipschitz property of real-valued functions , where the Lipschitz property is defined with respect to an arbitrary undirected graph $…
Agnostic proper learning of monotone functions: beyond the black-box correction barrier
Jane Lange, Arsen Vasilyan
We give the first agnostic, efficient, proper learning algorithm for monotone Boolean functions. Given uniformly random examples of an unknown…
Tester-Learners for Halfspaces: Universal Algorithms
Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first tester-learner for halfspaces that succeeds universally over a wide class of structured distributions. Our universal tester-learner runs in fully polynomial time…
An Efficient Tester-Learner for Halfspaces
Aravind Gollakota, Adam R. Klivans, Konstantinos Stavropoulos +1
We give the first efficient algorithm for learning halfspaces in the testable learning model recently defined by Rubinfeld and Vasilyan (2023). In this model, a learner certifies t…
Properly learning monotone functions via local reconstruction
Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan
We give a -time algorithm for properly learning monotone Boolean functions under the uniform distribution over . Our algorithm is robust to ad…
Testing distributional assumptions of learning algorithms
Ronitt Rubinfeld, Arsen Vasilyan
There are many high dimensional function classes that have fast agnostic learning algorithms when assumptions on the distribution of examples can be made, such as Gaussianity or un…
Monotone probability distributions over the Boolean cube can be learned with sublinear samples
Ronitt Rubinfeld, Arsen Vasilyan
A probability distribution over the Boolean cube is monotone if flipping the value of a coordinate from zero to one can only increase the probability of an element. Given samples o…
Approximating the noise sensitivity of a monotone Boolean function
Ronitt Rubinfeld, Arsen Vasilyan
The noise sensitivity of a Boolean function is one of its fundamental properties. A function of a positive noise parameter , it is denoted as…