Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
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