Abstract
We prove that poly-sized AC0 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(log2n)-independent distributions fool poly-size DNF formulas. [Razborov 2008] has later given a much simpler proof for Bazzi's theorem.
Original language | English (US) |
---|---|
Article number | 28 |
Journal | Journal of the ACM |
Volume | 57 |
Issue number | 5 |
DOIs | |
State | Published - Jun 2010 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
Keywords
- Circuit complexity
- Lower bounds
- Polynomial approximations
- Pseudorandomness