Bounded
Ilias Diakonikolas, Parikshit Gopalan,
Ragesh Jaiswal,
Rocco Servedio, Emanuele Viola
SIAM Journal on Computing (SICOMP), to appear
50th Annual Symposium on Foundations of Computer Science (FOCS), 2009
Abstract:
We show that any distribution on {-1, +1}n that is k-wise independent fools any halfspace h :{-1, +1}n →{-1, +1} with error ε for k = O ( log2(1/ε)/ε2 ). Our result is tight up to logarithmic 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 ε and seed length s = k ∙ log n = O (log n ∙ log2(1/ε)/ε2).
Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Computational Complexity, 2007).
Full version: [PDF]