2 citations · 2 across the 7 of their papers we have counts for
8 papers · 1 filter
Distribution-Free Halfspace Testing with Samples
Xi Chen, Renato Ferreira Pinto, Nathaniel Harms +2
We prove a tight lower bound on the number of samples required for testing halfspaces over , in the distribution-free sample-based model where the underlying…
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.…
Tight Bounds for Learning Polyhedra with a Margin
Shyamal Patel, Santosh Vempala
We give an algorithm for PAC learning intersections of halfspaces with a margin to within error that runs in time $\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1})…
Learning Functions of Halfspaces
Josh Alman, Shyamal Patel, Rocco A. Servedio
We give an algorithm that learns arbitrary Boolean functions of arbitrary halfspaces over , in the challenging distribution-free Probably Approximately Correct (P…
A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
Xi Chen, Shyamal Patel, Rocco A. Servedio
The main conceptual contribution of this paper is identifying a previously unnoticed connection between two central problems in computational learning theory and property testing:…
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
Xi Chen, Yumou Fei, Shyamal Patel
We give a distribution-free testing algorithm for decision lists with queries. This is the first sublinear algorithm for this problem, which sh…
New Lower Bounds for Adaptive Tolerant Junta Testing
Xi Chen, Shyamal Patel
We prove a lower bound for adaptively testing whether a Boolean function is -close to or -far from -j…
A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
Greg Bodwin, Shyamal Patel
We give a short and easy upper bound on the worst-case size of fault tolerant spanners, which improves on all prior work and is fully optimal at least in the setting of vertex faul…