## 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=1}^{n} w_{i}x_{i}-θ), where the w_{1},...,w_{n} and θ are arbitrary real numbers, with error ε for k=O(ε^{-2} log^{2}(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} log^{2}(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 language | English |
---|---|

Pages (from-to) | 3441-3462 |

Number of pages | 22 |

Journal | SIAM Journal on Computing |

Volume | 39 |

Issue number | 8 |

DOIs | |

Publication status | Published - 2010 |