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 - theta). We consider halfspaces over the continuous domain R(n) (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 epsilon-far from any halfspace using only poly(1/epsilon) queries, independent of the dimension n. Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: The first gives an exact relationship between the expected value of a halfspace f and the sum of the squares of f's degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube {-1, 1}(n) (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over {-1, 1}(n) poses significant additional complications and requires other ingredients. These include "cross-consistency" versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas [E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky, Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, 2002, pp. 103-112].
halfspaces fourier analysis linear threshold functions property testing