Bounded Independence fools halfspaces
- Ilias Diakonikolas ,
- Parikshit Gopalan ,
- Ragesh Jaiswal ,
- Rocco A. Servedio ,
- Emanuele Viola
FOCS'09 |
Published by IEEE
We show that any distribution on −1, +1n that is k-wise independent fools any Boolean halfspace function on n variables with error e for k = O(log2(1/e)). Up to logarithmic factors, our result matches a lower bound on k by Benjamini, Gurel-Gurevich, and Peled (2007). Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators that fool halfspaces.
© 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.http://www.ieee.org/