On Derandomizing Algorithms that Err Extremely Rarely

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 C (e.g., P/poly or AC0,AC0[2]) and a bounding function B: N → N (e.g., B(n) = nlog n or B(n) = exp(n0.99))), given an n-input circuit C from 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 C corresponds to the case of B(n) = 2n/2 (or to B(n) = 2n/3 for the two-sided version case). Our main results regarding the new quantified challenge are: 1. Solving the quantified derandomization challenge for the classAC0 and every sub-exponential bounding function (e.g., B(n) = exp(n0.999)). 2. Showing that solving the quantified derandomization challenge for the class AC0[2] and any sub-exponential bounding function (e.g., B(n) = exp(n0.001)), implies solving the standard derandomization challenge for the class AC0[2] (i.e., for B(n) = 2n/2)