On Medium-Uniformity and Circuit Lower Bounds

Rahul Santhanam, Ryan Williams

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

Abstract

We explore relationships between circuit complexity, the complexity of generating circuits, and algorithms for analyzing circuits. Our results can be divided into two parts: 1. Lower Bounds Against Medium-Uniform Circuits. Informally, a circuit class is “medium uniform” if it can be generated by an algorithmic process that is somewhat complex (stronger than LOGTIME) but not infeasible. Using a new kind of indirect diagonalization argument, we prove several new unconditional lower bounds against medium uniform circuit classes, including: ; For all k, P is not contained in P-uniform SIZE(nk). That is, for all k there is a language Lk ∈ P that does not have O(nk)-size circuits constructible in polynomial time. This improves Kannan's lower bound from 1982 that NP is not in P-uniform SIZE(nk) for any fixed k. ; For all k, NP is not in P||NP-uniform SIZE(nk). This also improves Kannan's theorem, but in a different way: the uniformity condition on the circuits is stronger than that on the language itself. ; For all k, LOGSPACE does not have LOGSPACE-uniform branching programs of size nk. 2. Eliminating Non-Uniformity and (Non-Uniform) Circuit Lower Bounds. We complement these results by showing how to convert any potential simulation of LOGTIME-uniform NC1 in ACC0/poly or TC0/poly into a medium-uniform simulation using small advice. This lemma can be used to simplify the proof that faster SAT algorithms imply NEXP circuit lower bounds, and leads to the following new connection: . Consider the following task: given a TC0 circuit C of nO(1) size, output yes when C is unsatisfiable, and output no when C has at least 2n-2 satisfying assignments. (Behavior on other inputs can be arbitrary.) Clearly, this problem can be solved efficiently using randomness. If this problem can be solved deterministical- y in 2n-ω(log n) time, then NEXP ⊄ TC0/poly. The lemma can also be used to derandomize randomized TC0 simulations of NC1 on almost all inputs: ; Suppose NC1 ⊆ BPTC0. Then for every ε > 0 and every language L in NC1, there is a (uniform) TC0 circuit family of polynomial size recognizing a language L' such that L and L' differ on at most 2nϵ inputs of length n, for all n.
Original languageEnglish
Title of host publicationProceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013
Pages15-23
Number of pages9
DOIs
Publication statusPublished - 2013

Fingerprint

Dive into the research topics of 'On Medium-Uniformity and Circuit Lower Bounds'. Together they form a unique fingerprint.

Cite this