Testing Halfspaces over Rotation-Invariant Distributions

Nathaniel Harms

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$…