On Uniformity and Circuit Lower Bounds

Rahul Santhanam*, Ryan Williams

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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(n (k) ). That is, for all k, there is a language that does not have O(n (k) )-size circuits constructible in polynomial time. This improves Kannan's lower bound from 1982 that NP is not in P-uniform SIZE(n (k) ) for any fixed k.

For all k, NP is not in .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 n (k) .

Eliminating non-uniformity and (non-uniform) circuit lower bounds. We complement these results by showing how to convert any potential simulation of LOGTIME-uniform NC (1) in ACC (0)/poly or TC (0)/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 TC (0) circuit C of n (O(1)) size, output yes when C is unsatisfiable, and output no when C has at least 2 (n-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 deterministically in 2 (n-omega(log) n) time, then NEXP not subset of TC degrees/poly.

Another application is to derandomize randomized TC degrees simulations of NC1 on almost all inputs:

Suppose . Then, for every epsilon > 0 and every language L in NC (1), there is a LOGTIME-uniform TC (0) circuit family of polynomial size recognizing a language L' such that L and L' differ on at most inputs of length n, for all n.

Original languageEnglish
Pages (from-to)177-205
Number of pages29
JournalComputational complexity
Volume23
Issue number2
Early online date16 May 2014
DOIs
Publication statusPublished - 30 Jun 2014

Keywords

  • Circuit complexity
  • uniformity
  • lower bounds
  • satisfiability algorithms
  • PSEUDORANDOM GENERATORS
  • POLYLOGARITHMIC TIME
  • COMPLEXITY
  • MACHINES

Fingerprint

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

Cite this