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 AC 0 , AC 0 [2]) and a bounding function B : N → N (e.g., B ( n ) = n log n or B ( n ) = exp( n 0.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 ) = 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.

Authors

• Oded Goldreich 0001
• Avi Wigderson

Keywords

• AC 0
• AC 0 [2]
• MA and AM
• Hastad's switching lemma
• approximate counting
• derandomization
• log-space
• pseudorandom generators