Seminar by Ragesh Jaiswal
Bounded Independence Fools Half-spaces
Ragesh Jaiswal
Columbia University
Date: Friday, December 4th, 2009
Time: 4:00 PM
Venue: CS101.
Abstract:
Halfspaces (a.k.a linear threshold functions), are an important class of boolean functions $h : \{\pm 1\}^n \rightarrow \{\pm 1\}$ of the form $h(x) = sgn(w_1x_1 + \ldots w_nx_n - \theta)$, where the weights $w_1, \ldots, w_n$ and the threshold $\theta$ are arbitrary real numbers. These functions have been studied extensively in a variety of contexts like computational complexity, learning theory and social choice theory.\\ In this work we make progress on a natural complexity-theoretic question about halfspaces. we show that any distribution on $\{-1, +1\}^n$ that is $k$-wise independent (A distribution ${ D}$ on $\{-1, +1\}^n$ is $k$-wise independent if the projection of $ D}$ on any $k$ indices is uniformly distributed over $\{-1, +1\}^k$.) fools (A distribution ${ D}$ is said to fool a halfspace $h$ with error $\epsilon$ if $|E_{x \leftarrow { D}} [h(x)] - E_{x \leftarrow {U}}[h(x)]| \leq \epsilon$, where ${ U}$ is the uniform distribution on $\{-1, +1\}^n$.) any halfspace with error $\epsilon$ for $k = O(\epsilon^{-2}\log^2(1/\epsilon))$. Our result is tight upto $\log(1/\epsilon)$ factors. Using standard constructions for $k$-wise independent distributions, we obtain the first explicit pseudorandom generators $G : \{-1, +1\}^s \rightarrow \{-1, +1\}^n$ that fools halfspaces. Specifically we fool halfspaces with error $\epsilon$ and seed length $s = k \cdot \log n = O(\log n \cdot \epsilon^{-2}\log^2(1/\epsilon))$.\\\\ Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Comput. Complexity 2007). This is joint work with Ilias Diakonikolas (Columbia University), Parikshit Gopalan (Microsoft Research), Rocco Servedio (Columbia University) and Emanuele Viola (Northeastern University).