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(Σ_i=1ⁿ w_ix_i-θ), where the w₁,...,w_n and θ are arbitrary real numbers, with error ε for k=O(ε^-2 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\}^s→{-1,+1}ⁿ that fool halfspaces. Specifically, we fool halfspaces with error ε and seed length s=k⋅log n=O(log n⋅ε^-2 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].