Search Mailing List Archives
[theory-seminar] Theory Lunch 4/21: Cody Murray on Circuit Lower Bounds
Dan Michael Stubbs
dstubbs at stanford.edu
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!
==================================
Title:
Easiness Amplification and Lower Bounds for Circuits Constructible in Small Space
Abstract:
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: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20160421/ea2e589d/attachment.html>
More information about the theory-seminar
mailing list