A Simple Proof of Bazzi's Theorem

Time
2:00pm – 2:50pm, Friday, April 17, 2009
Place
CSE 203
Speaker
Alexander Razborov (UChicago and IAS)

Abstract

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.