13 citations · 14 across the 19 of their papers we have counts for
5 papers · 1 filter
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…