## Abstract / Description of output

A family of Boolean circuits TeX is called γ(n)-weakly uniform if there is a polynomial-time algorithm for deciding the direct-connection language of every C n , given advice of size γ(n). This is a relaxation of the usual notion of uniformity, which allows one to interpolate between complete uniformity (when γ(n) = 0) and complete non-uniformity (when γ(n) > |C n |). Weak uniformity is essentially equivalent to succinctness introduced by Jansen and Santhanam [12].

Our main result is that Permanent is not computable by polynomial-size n o(1)-weakly uniform TC 0 circuits. This strengthens the results by Allender [2] (for uniform TC 0) and by Jansen and Santhanam [12] (for weakly uniform arithmetic circuits of constant depth). Our approach is quite general, and can be used to extend to the “weakly uniform” setting all currently known circuit lower bounds proved for the “uniform” setting. For example, we show that Permanent is not computable by polynomial-size (logn) O(1)-weakly uniform threshold circuits of depth o(loglogn), generalizing the result by Koiran and Perifel [16].

Our main result is that Permanent is not computable by polynomial-size n o(1)-weakly uniform TC 0 circuits. This strengthens the results by Allender [2] (for uniform TC 0) and by Jansen and Santhanam [12] (for weakly uniform arithmetic circuits of constant depth). Our approach is quite general, and can be used to extend to the “weakly uniform” setting all currently known circuit lower bounds proved for the “uniform” setting. For example, we show that Permanent is not computable by polynomial-size (logn) O(1)-weakly uniform threshold circuits of depth o(loglogn), generalizing the result by Koiran and Perifel [16].

Original language | English |
---|---|

Title of host publication | Computing and Combinatorics |

Subtitle of host publication | 18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings |

Publisher | Springer Berlin Heidelberg |

Pages | 408-419 |

Number of pages | 12 |

Volume | 7434 |

ISBN (Electronic) | 978-3-642-32241-9 |

ISBN (Print) | 978-3-642-32240-2 |

DOIs | |

Publication status | Published - 2012 |