多対数独立性はAC⁰回路を欺く

多項サイズのAC 0回路は、多対数独立分布を一様分布と区別できないことを証明します。これは、LinialとNisanによる1990年の予想を解決します。この問題に関する唯一の以前の進展は、Bazzi Baz07によるもので、O(log 2 n)-独立分布が多項サイズのDNF式を欺くことを示しました。Razborov Raz08は、その後、Bazzipsilas定理のためのはるかに簡単な証明を提供しました。