On Derandomizing Algorithms that Err Extremely Rarely
Webpage for a paper by Oded Goldreich and Avi Wigderson
Abstract
Does derandomization of probabilistic algorithms become easier
when the number of ``bad'' random inputs is extremely small?
In relation to the above question, we put forward the following
quantified derandomization challenge:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$)
and a bounding function $B:\N\to\N$
(e.g., $B(n)=n^{\log n}$ or $B(n)=\exp(n^{0.99}))$),
given an $n$-input circuit $C$ from $\cal C$
that evaluates to 1 on all but at most $B(n)$ of its inputs,
find (in deterministic polynomial-time) an input $x$ such that $C(x)=1$.
Indeed, the standard derandomization challenge for the class $\calC$
corresponds to the case of $B(n)=2^n /2$
(or to $B(n)=2^n /3$ for the two-sided version case).
Our main results regarding the new quantified challenge are:
-
Solving the quantified derandomization challenge
for the class $AC^0$ and every sub-exponential bounding function
(e.g., $B(n)=\exp(n^{0.999})$).
-
Showing that solving the quantified derandomization challenge
for the class $AC^0[2]$ and any sub-exponential bounding function
(e.g., $B(n)=\exp(n^{0.001})$), implies solving the standard
derandomization challenge for the class $AC^0[2]$ (i.e., for $B(n)=2^n/2$).
Analogous results are obtained also for stronger (Black-box) forms of
efficient derandomization like hitting-set generators.
We also obtain results for other classes of computational
devices including log-space algorithms and Arithmetic circuits.
For the latter we present a deterministic polynomial-time
hitting set generator for the class of $n$-variate polynomials
of degree $d$ over $GF(2)$ that evaluate to 0 on at most
an $O(2^{-d})$ fraction of their inputs.
In general, the quantified derandomization problem raises
a variety of seemingly unexplored questions about many randomized
complexity classes, and may offer a tractable approach to unconditional
derandomization for some of them.
Material available on-line
Back to
either Oded Goldreich's homepage
or general list of papers.
