Bounded Independence Fools Halfspaces

I. Diakonikolas, P. Gopalan, R. Jaiswal, R. Servedio, E. Viola

Research output: Contribution to journalArticlepeer-review

Abstract

We show that any distribution on {-1,+1}n that is k-wise independent fools any halfspace (or linear threshold function) h:{-1,+1\}n→{-1,+1}, i.e., any function of the form h(x)=sign(Σi=1n wixi-θ), where the w1,...,wn and θ are arbitrary real numbers, with error ε for k=O(ε-2 log2(1/ε)). Our result is tight up to log(1/ε) factors. 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 ε and seed length s=k⋅log n=O(log n⋅ε-2 log2(1/ε)). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio [Comput. Complexity, 16 (2007), pp. 180–209].

Original languageEnglish
Pages (from-to)3441-3462
Number of pages22
JournalSIAM Journal on Computing
Volume39
Issue number8
DOIs
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'Bounded Independence Fools Halfspaces'. Together they form a unique fingerprint.

Cite this