Distribution-Free Halfspace Testing with Samples

Xi Chen, Renato Ferreira Pinto, Nathaniel Harms +2

We prove a tight $\Theta (n/\epsilon )$ lower bound on the number of samples required for testing halfspaces over ${\mathbb{R}}^n$, in the distribution-free sample-based model where the underlying…