Bounded Independence Fools Halfspaces Export

@article{citeulike:5035406, abstract = {We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps) /\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). 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 eps and seed length s = k \log n = O(\log n \cdot \log^2(1/\eps) /\eps^2). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Computational Complexity 2007).}, archivePrefix = {arXiv}, author = {Diakonikolas, Ilias and Gopalan, Parikshit and Jaiswal, Ragesh and Servedio, Rocco and Viola, Emanuele}, citeulike-article-id = {5035406}, citeulike-linkout-0 = {http://arxiv.org/abs/0902.3757v1}, citeulike-linkout-1 = {http://arxiv.org/pdf/0902.3757v1}, comment = {A distribution ϵ-fools a function if ϵ bounds the difference between the expected value of the function on the fooling distribution and the expected value of the function on a uniform distribution. A distribution on sign-valued vectors need only be k-wise independent to fool a halfspace.}, day = {21}, eprint = {0902.3757v1}, keywords = {approximation, computational\_learning\_theory, linearity}, month = {Feb}, posted-at = {2009-07-01 19:18:58}, priority = {2}, title = {Bounded Independence Fools Halfspaces}, url = {http://arxiv.org/abs/0902.3757v1}, year = {2009} }

TY - JOUR ID - citeulike:5035406 L3 - citeulike-article-id:5035406 N2 - We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps) /\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = \Omega(1/(\eps^2 \cdot \log(1/\eps))). 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 eps and seed length s = k \log n = O(\log n \cdot \log^2(1/\eps) /\eps^2). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Computational Complexity 2007). TI - Bounded Independence Fools Halfspaces KW - approximation KW - computational_learning_theory KW - linearity N1 - A distribution ϵ-fools a function if ϵ bounds the difference between the expected value of the function on the fooling distribution and the expected value of the function on a uniform distribution. A distribution on sign-valued vectors need only be k-wise independent to fool a halfspace. AU - Diakonikolas, Ilias AU - Gopalan, Parikshit AU - Jaiswal, Ragesh AU - Servedio, Rocco AU - Viola, Emanuele PY - 2009/Feb/21/ UR - http://arxiv.org/abs/0902.3757v1 ER -