We show that any distribution on ${-1,1}^n$ that is $k$-wise independent fools any halfspace $h : {-1,1}^n \to {-1,1}$, i.e., any function of the form $h(x) = \sign(\sum_{i = 1}^n w_i x_i - \theta)$ where the $w_1,\ldots,w_n,\theta$ are arbitrary real numbers, with error $\eps$ for $k = O(\eps^{-2}\log^2(1/\eps))$. Our result is tight up to $\log(1/\eps)$ factors. Using standard constructions of $k$-wise independent distributions, we obtain the first explicit pseudorandom generators $G : {-1,1}^s \to {-1,1}^n$ that fool halfspaces. Specifically, we fool halfspaces with error $\eps$ and seed length $s = k \cdot \log n = O(\log n \cdot \eps^{-2} \log^2(1/\eps))$.
Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput.~Complexity 2007).
pdf of conference version
pdf of full version