BOUNDED INDEPENDENCE FOOLS HALFSPACES
We show that any distribution on {-1, + 1}(n) that is k-wise independent fools any halfspace (or linear threshold function) h : {-1, + 1}(n) -> {-1, + 1}, i.e., any function of the form h(x) = sign(Sigma(n)(i=1) wixi - theta), where the w(1), ... , w(n) and theta are arbitrary real numbers, with error epsilon for k = O(epsilon(-2) log(2)(1/epsilon)). Our result is tight up to log(1/epsilon) 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 epsilon and seed length s = k . log n = O(log n . epsilon(-2) log2(1/epsilon)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio [Comput. Complexity, 16 (2007), pp. 180-209].
halfspace linear threshold function k-wise independent distribution pseudorandom generator