## On Derandomizing Algorithms that Err Extremely Rarely

#### 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:

1. Solving the quantified derandomization challenge for the class $AC^0$ and every sub-exponential bounding function (e.g., $B(n)=\exp(n^{0.999})$).
2. 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.