Bounded Independence fools halfspaces

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

Abstract

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.

Details

Publication typeInproceedings
Published inFOCS'09
PublisherIEEE
> Publications > Bounded Independence fools halfspaces