ECCC-Report TR07-128https://eccc.weizmann.ac.il/report/2007/128Comments and Revisions published for TR07-128en-usSat, 08 Dec 2007 15:24:51 +0200
Paper TR07-128
| Testing Halfspaces |
Kevin Matulef,
Ryan O'Donnell,
Ronitt Rubinfeld,
Rocco Servedio
https://eccc.weizmann.ac.il/report/2007/128This 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 &#8901; x - &#952;). 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 &#949;-far from any halfspace using only poly(1/&#949;) queries, independent of the dimension n.
<p>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 [FKR+:02].</p>
Sat, 08 Dec 2007 15:24:51 +0200https://eccc.weizmann.ac.il/report/2007/128