Bounded Independence Fools Halfspaces
I. Diakonikolas and P. Gopalan and R. Jaiswal and R. Servedio and E. Viola.
SIAM Journal on Computing, 39(8), 2010, pp. 3441-3462.
Preliminary version in 50th Annual Symposium on Foundations of Computer Science (FOCS), 2009, pp. 171--180.


Abstract:

We show that any distribution on ${-1,1}^n$ that is $k$-wise independent fools any halfspace $h : {-1,1}^n \to {-1,1}$, i.e., any function of the form $h(x) = \sign(\sum_{i = 1}^n w_i x_i - \theta)$ where the $w_1,\ldots,w_n,\theta$ are arbitrary real numbers, with error $\eps$ for $k = O(\eps^{-2}\log^2(1/\eps))$. Our result is tight up to $\log(1/\eps)$ factors. Using standard constructions of $k$-wise independent distributions, we obtain the first explicit pseudorandom generators $G : {-1,1}^s \to {-1,1}^n$ that fool halfspaces. Specifically, we fool halfspaces with error $\eps$ and seed length $s = k \cdot \log n = O(\log n \cdot \eps^{-2} \log^2(1/\eps))$.

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

pdf of conference version

pdf of full version


Back to main papers page