Testing Halfspaces

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x) = sgn(w∙x−Θ):We consider halfspaces over the continuous domain Rⁿ (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1; 1}ⁿ (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are ε-far from any halfspace using only poly( 1/ε) queries, independent of the dimension n.