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