Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-069 | 14th March 2012 00:50

Uniform Derandomization from Pathetic Lower Bounds

RSS-Feed




Revision #1
Authors: Eric Allender, Vikraman Arvind, Rahul Santhanam, Fengming Wang
Accepted on: 14th March 2012 00:51
Downloads: 900
Keywords: 


Abstract:

The notion of probabilistic computation dates back at least to Turing, and he
also wrestled with the practical problems of how to implement probabilistic
algorithms on machines with, at best, very limited access to randomness.
A more recent line of research, known as derandomization, studies the extent
to which randomness is superfluous.
A recurring theme in the literature on derandomization is that probabilistic
algorithms can be simulated quickly by deterministic algorithms, if one
can obtain impressive (i.e., superpolynomial, or even nearly-exponential)
circuit size lower bounds for certain problems. In contrast to what is
needed for derandomization, existing lower bounds seem rather pathetic
(linear-size lower bounds for general circuits, nearly cubic lower bounds for formula size, nearly quadratic size lower bounds for branching programs,
$n^{1+c_d}$ for depth $d$ threshold circuits).

Here, we present two instances where ``pathetic'' lower bounds of the form
$n^{1+\epsilon}$ would suffice to derandomize interesting classes of probabilistic algorithms.

We show:
* If the word problem over $S_5$ requires constant-depth threshold circuits
of size $n^{1+\epsilon}$ for some $\epsilon > 0$, then any language
accepted by uniform polynomial-size probabilistic threshold circuits
can be solved in subexponential time (and more strongly, can be
accepted by a uniform family of deterministic constant-depth threshold
circuits of subexponential size.)

* If there are no constant-depth arithmetic circuits of size $n^{1+\epsilon}$ for the problem of multiplying a sequence of $n$
3-by-3 matrices, then for every constant $d$, black-box identity testing
for depth-$d$ arithmetic circuits with bounded individual degree
can be performed in subexponential time (and even by
a uniform family of deterministic constant-depth
AC$^0$ circuits of subexponential size).


Paper:

TR10-069 | 17th April 2010 05:04

Uniform Derandomization from Pathetic Lower Bounds





TR10-069
Authors: Eric Allender, Vikraman Arvind, Fengming Wang
Publication: 17th April 2010 05:05
Downloads: 1608
Keywords: 


Abstract:

A recurring theme in the literature on derandomization is that probabilistic
algorithms can be simulated quickly by deterministic algorithms, if one can obtain *impressive* (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is
needed for derandomization, existing lower bounds seem rather pathetic (linear-size lower bounds for general circuits, nearly cubic lower bounds for formula size, nearly n loglog n size lower bounds for branching programs,
$n^{1+c_d}$ for depth d threshold circuits).

Here, we present two instances where ``pathetic'' lower bounds of the form
$n^{1+\epsilon}$ would suffice to derandomize interesting classes of
probabilistic algorithms.

We show:
* If the word problem over $S_5$ requires constant-depth threshold circuits
of size $n^{1+\epsilon}$ for some $\epsilon > 0$, then any language
accepted by uniform polynomial-size probabilistic threshold circuits
can be solved in subexponential time (and more strongly, can be
accepted by a uniform family of deterministic constant-depth threshold
circuits of subexponential size.)

* If there are no constant-depth arithmetic circuits of size $n^{1+\epsilon}$ for the problem of multiplying a sequence of $n$
3-by-3 matrices, then for every constant $d$, black-box identity testing
for depth-$d$ arithmetic circuits with bounded individual degree
can be performed in subexponential time (and even by
a uniform family of deterministic constant-depth
AC$^0$ circuits of subexponential size).


Comment(s):

Comment #1 to TR10-069 | 19th December 2012 10:31

Clarification about Permutation Problems complete for L





Comment #1
Authors: Eric Allender, Vikraman Arvind, Rahul Santhanam, Fengming Wang
Accepted on: 19th December 2012 10:31
Downloads: 777
Keywords: 


Abstract:

It has been pointed out to us that it is not immediately obvious that the version of the L-complete permutation problem that we use is equivalent to the one proved complete by Cook and McKenzie. In this comment, we provide the missing details.




ISSN 1433-8092 | Imprint