file.pdf (485.55 kB)
Download file

Testing Halfspaces

Download (485.55 kB)
journal contribution
posted on 01.01.1983, 00:00 authored 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



Usage metrics