The Taub Faculty of Computer Science Events and Talks

Invariance principles or limit theorems have recently found several important applications in theoretical computer science. In this talk I'll present some recent results with the broad theme of constructing pseudorandom generators from invariance principles. The first set of results concerns the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n/eps^{O(d)}$ fooling degree d PTFs with error at most eps. Previously, no nontrivial constructions were known even for quadratic threshold functions and constant error eps. For the class of degree 1 threshold functions or halfspaces, we construct PRGs with much better dependence on the error parameter eps and obtain a PRG with seed-length O(log n + log^2(1/eps)). The second set of results concerns "discrete central limit theorems", and fooling linear forms over 0-1 inputs in total variation distance.

Joint work with David Zuckerman; Parikshit Gopalan, Omer Reingold and David Zuckerman.