Projects per year
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 MediumUniform 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 Puniform 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 Puniform SIZE(nk) for any fixed k. ; For all k, NP is not in PNPuniform 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 LOGSPACEuniform branching programs of size nk. 2. Eliminating NonUniformity and (NonUniform) Circuit Lower Bounds. We complement these results by showing how to convert any potential simulation of LOGTIMEuniform NC1 in ACC0/poly or TC0/poly into a mediumuniform 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 2n2 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 language  English 

Title of host publication  Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 57 June, 2013 
Pages  1523 
Number of pages  9 
DOIs  
Publication status  Published  2013 
Fingerprint
Dive into the research topics of 'On MediumUniformity and Circuit Lower Bounds'. Together they form a unique fingerprint.Projects
 1 Finished

Hierarchies, Circuit Lower Bounds and Pseudorandomness
Santhanam, R.
1/10/10 → 31/12/12
Project: Research