Bounded Independence Fools Halfspaces

We show that any distribution on {-1, +1} n that is k-wise independent fools any halfspace (a. k. a. threshold) h: {-1, +1} n ¿ {-1, +1}, i. e. , any function of the form h(x) = sign(¿ i=1 n w i X i - ¿) where the w 1, .. ., w n, ¿ are arbitrary real numbers, with error ¿ for k = O(¿ -2 log 2 (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} n that fool halfspaces. Specifically, we fool halfspaces with error e and seed length s = k · log n = O(log n · ¿ -2 log 2 (1/¿)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput. Complexity 2007).

Authors

• Ilias Diakonikolas
• Parikshit Gopalan
• Ragesh Jaiswal
• Rocco A. Servedio
• Emanuele Viola

Keywords

• Circuits
• Computer science
• Game theory
• Silicon
• Educational institutions
• Information science
• Approximation methods
• Boosting
• Support vector machines
• Voting
• Approximation Theory
• Error Bounds
• Critical Indicator
• Small Circuit
• Univariate Polynomial
• halfspaces
• pseudorandomness
• k-wise independent distributions