Lower Bounds against Weakly Uniform Circuits

Ruiwen Chen, Valentine Kabanets

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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].
Original languageEnglish
Title of host publicationComputing and Combinatorics
Subtitle of host publication18th Annual International Conference, COCOON 2012, Sydney, Australia, August 20-22, 2012. Proceedings
PublisherSpringer Berlin Heidelberg
Pages408-419
Number of pages12
Volume7434
ISBN (Electronic)978-3-642-32241-9
ISBN (Print)978-3-642-32240-2
DOIs
Publication statusPublished - 2012

Fingerprint

Dive into the research topics of 'Lower Bounds against Weakly Uniform Circuits'. Together they form a unique fingerprint.

Cite this