Bounded Independence Fools Halfspaces

We show that any distribution on {-1,+1} n that is k-wise independent fools any halfspace (a.k.a. threshold) h : {-1,+1} n ¿ {-1,+1}, i.e., any function of the form h(x) = sign(¿ i=1 n w i X i - ¿) where the w 1 ,..., w n , ¿ are arbitrary real numbers, with error ¿ for k = O(¿ -2 log 2 (1/¿)). Our result is tight up to log(1/¿) factors. Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators G : {-1,+1} s ¿ {-1,+1} n that fool halfspaces. Specifically, we fool halfspaces with error e and seed length s = k · log n = O(log n · ¿ -2 log 2 (1/¿)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput. Complexity 2007).