REPORTS > DETAIL:
Paper:
TR08-081 | 11th September 2008 00:00
A simple proof of Bazzi's theorem
TR08-081 Authors: Alexander Razborov
Publication: 11th September 2008 21:19
Downloads: 285
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.