Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Pseudorandom Generators from Invariance Principles
event speaker icon
Raghu Meka (University of Texas at Austin)
event date icon
Sunday, 09.01.2011, 12:30
event location icon
Taub 539
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.