דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Pseudorandom Generators from Invariance Principles
event speaker icon
ראגו מקה (אונ' טקסס באוסטין)
event date icon
יום ראשון, 9.1.2011, 12:30
event location icon
טאוב 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.
[בחזרה לאינדקס האירועים]