Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 4/21: Cody Murray on Circuit Lower Bounds

Dan Michael Stubbs dstubbs at
Wed Apr 20 18:54:13 PDT 2016

Hi all,

The theory lunch speaker this week will be Cody Murray.  As usual, food will be available around 12:15pm and the talk will begin at 12:30pm in Gates 463A this Thursday.

Be there!


Easiness Amplification and Lower Bounds for Circuits Constructible in Small Space

We give striking new consequences of the assumption that time-bounded algorithms can be ``compressed'' with non-uniform circuits. Our main tool is an ``easiness amplification'' lemma for circuits: if n^(1+e) time computations have quasilinear size (non-uniform) circuits for some e > 0, then every problem solvable in polynomial time and subpolynomial space has quasilinear size (non-uniform) circuits as well. Consequences include:

* An easy problem without small LOGSPACE-uniform circuits.  Circuits whose descriptions can be produced by an O(log n)-space algorithm are called LOGSPACE-uniform. As it is open whether NP = L, few results are known about the limits of logspace computations.
For all e > 0, we give a natural problem General CIrcuit-n^e-Composition which is computable in n^(1+e) time, but we prove it is not in LOGSPACE-uniform n^(1+o(1)) size: arbitrary poly-time and log-space preprocessing cannot produce n^(1+o(1))-size circuits for this problem.

* Problems without small LOGSPACE-uniform circuits of log-depth. For every e > 0, 1 < d < 2, and d' < d we give another natural problem (log n)^d-Depth Circuit n^e-Composition} computable in O(n^(1+e) ) time, or in O((log n)^d) space (though not necessarily simultaneously) that we prove does not have SPACE[(log n)^d']-uniform circuits of quasilinear size and O((log n)^d' ) depth. Turning our attention to NP-hard problems, we also show that SAT does not have circuits of quasilinear size and log^(2-o(1)) n depth that are constructible in log^(2-o(1)) n space. The depth lower bound is a nearly-quadratic improvement over prior results of this kind.

* A strong circuit complexity amplification. For every e > 0, we give a natural problem Circuit n^e-Composition and show that if it has quasilinear-size circuits (uniform or not), then every problem solvable in 2^( O(n) ) time and 2^( O(sqrt(n) \log n) ) space (simultaneously) has 2^(O(sqrt(n) log n) )-size circuits (uniform or not). We also show same consequence holds assuming SAT has quasilinear-size circuits.
As a corollary, if n^1.1 time computations (or O(n) nondeterministic time computations) have quasilinear-size circuits, then all problems in exponential time and subexponential space (such as quantified Boolean formulas) have significantly subexponential-size circuits. This is a new connection between the relative circuit complexities of easy and hard problems.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list