Bounded Independence Fools Halfspaces

We show that any distribution on \-1,+1\ⁿ that is k-wise independent fools any halfspace (or linear threshold function) h:\-1,+1\ⁿ→\-1,+1\, i.e., any function of the form h(x)=sign(∑ᵢ₌₁ⁿwᵢxᵢ-θ), where the w₁,,wₙ and θ are arbitrary real numbers, with error ε for k=O(ε⁻²log²(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\ˢ→\-1,+1\ⁿ that fool halfspaces. Specifically, we fool halfspaces with error ε and seed length s=k·log n=O(log n·ε⁻²log²(1/ε)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio [Comput. Complexity, 16 (2007), pp. 180–209].