Bounded Independence Fools Halfspaces

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal +2

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…