ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-081 | 11th September 2008 00:00

A simple proof of Bazzi's theorem

RSS-Feed




TR08-081
Authors: Alexander Razborov
Publication: 11th September 2008 21:19
Downloads: 1005
Keywords: 


Abstract:

In 1990, Linial and Nisan asked if any polylog-wise independent distribution fools any function in AC^0. In a recent remarkable development, Bazzi solved this problem for the case of DNF formulas.
The aim of this note is to present a simplified version of his proof.



ISSN 1433-8092 | Imprint