A Simple Proof of Bazzi’s Theorem
Alexander Alexandrovich Razborov · ACM Transactions on Computation Theory · 2009
Linial and Nisan [1990] 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.