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 polynomialtime) 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 twosided version case).
Our main results regarding the new quantified challenge are:

Solving the quantified derandomization challenge
for the class $AC^0$ and every subexponential 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 subexponential 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 (Blackbox) forms of
efficient derandomization like hittingset generators.
We also obtain results for other classes of computational
devices including logspace algorithms and Arithmetic circuits.
For the latter we present a deterministic polynomialtime
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 online
Back to
either Oded Goldreich's homepage
or general list of papers.