Computer Science/Discrete Mathematics Seminar I | |

Topic: | Fooling intersections of low-weight halfspaces |

Speaker: | Rocco Servedio |

Affiliation: | Columbia University |

Date: | Monday, October 30 |

Time/Room: | 11:00am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2017/1030-RoccoServedio |

A weight-$t$ halfspace is a Boolean function $f(x)=\mathrm{sign}(w_1 x_1 + \cdots + w_n x_n - \theta)$ where each $w_i$ is an integer in $\{-t,\dots,t\}.$ We give an explicit pseudorandom generator that $\delta$-fools any intersection of $k$ weight-$t$ halfspaces with seed length poly$(\log n, \log k,t,1/\delta)$. In particular, our result gives an explicit PRG that fools any intersection of any quasipoly$(n)$ number of halfspaces of any polylog$(n)$ weight to any $1/$polylog$(n)$ accuracy using seed length polylog$(n).$ Prior to this work no explicit PRG with seed length $o(n)$ was known even for fooling intersections of $n$ weight-1 halfspaces to constant accuracy. Our analysis introduces new coupling-based ingredients into the standard Lindeberg method for establishing quantitative central limit theorems and associated pseudorandomness results. Joint work with Li-Yang Tan.