Bounded Independence Fools Halfspaces
Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio, Emanuele Viola

SIAM Journal on Computing (SICOMP), 39(8): 3441-3462, 2010

50th Annual Symposium on Foundations of Computer Science (FOCS), 2009



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 nlog2(1/ε)/ε2).


Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Computational Complexity, 2007).


Full version: [PDF]


Back to all papers page