Pseudorandom Generators and Typically-Correct Derandomization
by Jeff Kinne, Dieter van Melkebeek and Ronen Shaltiel
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
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
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.
list of Oded's choices