Abstract

We show that any distribution on −1, +1n that is k-wise independent fools any Boolean halfspace function on n variables with error e for k = O(log2(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.