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:

  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.