file.pdf (485.55 kB)

Testing Halfspaces

Download (485.55 kB)
journal contribution
posted on 01.01.1983 by Kevin Matulef, Ryan O'Donnell, Ronitt Rubenfeld, Rocco A. Servedio
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 Rn (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1; 1}n (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.


Publisher Statement

All Rights Reserved