{\em 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 {\em quantified derandomization challenge}:For a class of circuits (e.g., P/poly or AC0AC0[2] ) and a bounding function B:\N\N (e.g., B(n)=nlogn or B(n)=exp(n099))),given an n-input circuit C from 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 {\em standard}\/ derandomization challenge for the class corresponds to the case of B(n)=2n2 (or to B(n)=2n3 for the two-sided version case).Our main results regarding the new {\em quantified}\/ challenge are:

\begin{enumerate}\itemSolving the {\em quantified}\/ derandomization challenge for the class AC0 and every sub-exponential bounding function (e.g., B(n)=exp(n0999)).\itemShowing that solving the {\em quantified}\/ derandomization challenge for the class AC0[2] and any sub-exponential bounding function (e.g., B(n)=exp(n0001)), implies solving the {\em standard}\/ derandomization challenge for the class AC0[2] (i.e., for B(n)=2n2 ).\end{enumerate}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 mostan O(2−d) fraction of their inputs.

In general, the quantified derandomization problem raises a variety of seemingly unexplored questions about many randomizedcomplexity classes, and may offer a tractable approach to unconditional derandomization for some of them.