Revision #1 Authors: Eric Allender, Vikraman Arvind, Rahul Santhanam, Fengming Wang

Accepted on: 14th March 2012 00:51

Downloads: 2601

Keywords:

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).

TR10-069 Authors: Eric Allender, Vikraman Arvind, Fengming Wang

Publication: 17th April 2010 05:05

Downloads: 3866

Keywords:

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 #1 Authors: Eric Allender, Vikraman Arvind, Rahul Santhanam, Fengming Wang

Accepted on: 19th December 2012 10:31

Downloads: 2927

Keywords:

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.