## Abstract

We prove that poly-sized AC^{0} circuits cannot distinguish a poly-logarithmically independent distribution from the uniform one. This settles the 1990 conjecture by Linial and Nisan [LN90]. The only prior progress on the problem was by Bazzi [Baz07], who showed that O(log^{2}n)- independent distributions fool poly-size DNF formulas. Razborov [Raz08] has later given a much simpler proof for Bazzi's theorem.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 |

Pages | 3-8 |

Number of pages | 6 |

DOIs | |

State | Published - 2009 |

Externally published | Yes |

Event | 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 - Paris, France Duration: Jul 15 2009 → Jul 18 2009 |

### Publication series

Name | Proceedings of the Annual IEEE Conference on Computational Complexity |
---|---|

ISSN (Print) | 1093-0159 |

### Other

Other | 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009 |
---|---|

Country/Territory | France |

City | Paris |

Period | 7/15/09 → 7/18/09 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Computational Mathematics

## Fingerprint

Dive into the research topics of 'Poly-logarithmic independence fools AC^{0}circuits'. Together they form a unique fingerprint.