Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

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

#### Uniform Derandomization from Pathetic Lower Bounds

Revision #1
Authors: Eric Allender, Vikraman Arvind, Rahul Santhanam, Fengming Wang
Accepted on: 14th March 2012 00:51
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
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
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