A simple proof of Bazzi
Speaker: Alexander Razborov , University of Chicago
Date: February 25 2009
Time: 4:15PM to 5:15PM
Location: NOTE: 32-124
Host: Scott Aaronson, CSAIL
Contact: be, 3-6098, imbe@mit.edu
Relevant URL: > Pseudo-random generators that are secure against constant depth polynomial size circuits have been
> known since the seminal paper by Ajtai and Wigderson (1985). All available constructions of such
> generators, however, appear to be somewhat special and ad hoc. In 1990, Linial and Nisan made a
> bold and elegant conjecture stating that this property is in fact possessed by any generator in which
> any selection of polylogarithmically many output bits is independent; explicit constructions of such generators
> are abundant. This conjecture turned out surprisingly difficult, and
> it was only a couple of years ago that
> Bazzi proved it for the case of DNF formulas. Very recently the
> Nisan-Linial conjecture was completely solved in another breakthrough
> development by Braverman.
>
> The main purpose of our talk is to present a contribution that was
> intermediate between these two results. Namely, we give a
> substantially simplified version of Bazzi's argument, and we hope to present almost all details of our proof.
See other events that are part of Theory Colloquium 2008/2009
See other events happening in February 2009
