We show that any distribution on {−1, +1}^n that is k-wise independent fools any Boolean halfspace function on $n$ variables with error e for k = O(log^2(1/e)). Up to logarithmic factors, our result matches a lower bound on k by Benjamini, Gurel-Gurevich, and Peled (2007). Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators that fool halfspaces.

PDF file

Details