Testing Halfspaces over Rotation-Invariant Distributions
  We present an algorithm for testing halfspaces over arbitrary, unknown
rotation-invariant distributions. Using $\tilde O(\sqrt{n}\epsilon^{-7})$
random examples of an unknown function $f$, the algorithm determines with high
probability whether $f$ is of the form $f(x) = sign(\sum_i w_ix_i-t)$ or is
$\epsilon$-far from all such functions. This sample size is significantly
smaller than the well-known requirement of $\Omega(n)$ samples for learning
halfspaces, and known lower bounds imply that our sample size is optimal (in
its dependence on $n$) up to logarithmic factors. The algorithm is
distribution-free in the sense that it requires no knowledge of the
distribution aside from the promise of rotation invariance. To prove the
correctness of this algorithm we present a theorem relating the distance
between a function and a halfspace to the distance between their centers of
mass, that applies to arbitrary distributions.
