### Polylogarithmic independence fools $AC^{0}$ circuitsPolylogarithmic independence fools $AC^{0}$ circuits

Access Restriction
Subscribed

 Author Braverman, Mark Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2010 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Circuit complexity ♦ Lower bounds ♦ Polynomial approximations ♦ Pseudorandomness Abstract We prove that poly-sized $AC^{0}$ circuits cannot distinguish a polylogarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [1990]. The only prior progress on the problem was by Bazzi [2007], who showed that $O(log^{2}$ $\textit{n})-independent$ distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2008-06-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 57 Issue Number 5 Page Count 10 Starting Page 1 Ending Page 10

#### Open content in new tab

Source: ACM Digital Library