### 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 - Nov 9 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 | 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<sup>0</sup> circuits'. Together they form a unique fingerprint.

## Cite this

Braverman, M. (2009). Poly-logarithmic independence fools AC

^{0}circuits. In*Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity, CCC 2009*(pp. 3-8). [5231177] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2009.35