Pseudorandom Generators and Typically-Correct Derandomization

by Jeff Kinne, Dieter van Melkebeek and Ronen Shaltiel

Oded's comments

This work presents interesting results regarding "typically correct" derandomizations. On the positive side, it gets rid of the use of randomness extractors in this context, showing that a certain type of PRGs, called "seed extending PRGs" is all that is needed. (It should be noted that the NW-type PRGs are all seed extending, and it is actually instructive to note this fact in any exposition of the NW construction.) On the negative side, it is shown that typically-correct derandomization (with sufficiently small number of errors; e.g., as achieved in prior conditional results) imply circuit lower bounds very much as the implication known for the standard derandomization.

The original abstract

The area of derandomization attempts to provide efficient deterministic simulations of randomized algorithms in various algorithmic settings. Goldreich and Wigderson introduced a notion of ``typically-correct'' deterministic simulations, which are allowed to err on few inputs. In this paper we further the study of typically-correct derandomization in two ways. First, we develop a generic approach for constructing typically-correct derandomizations based on seed-extending pseudorandom generators, which are pseudorandom generators that reveal their seed. We use our approach to obtain both conditional and unconditional typically-correct derandomization results in various algorithmic settings. We show that our technique strictly generalizes an earlier approach by Shaltiel based on randomness extractors, and simplifies the proofs of some known results. We also demonstrate that our approach is applicable in algorithmic settings where earlier work did not apply. For example, we present a typically-correct polynomial-time simulation for every language in BPP based on a hardness assumption that is weaker than the ones used in earlier work. Second, we investigate whether typically-correct derandomization of BPP implies circuit lower bounds. Extending the work of Kabanets and Impagliazzo for the zero-error case, we establish a positive answer for error rates in the range considered by Goldreich and Wigderson. In doing so, we provide a simpler proof of the zero-error result. Our proof scales better than the original one and does not rely on the result by Impagliazzo, Kabanets, and Wigderson that NEXP having polynomial-size circuits implies that NEXP coincides with EXP.

Back to list of Oded's choices.