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 \cdot 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(\frac{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 $\bits^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 \cite{FKR+:02}.