We show how to simulate any BPP algorithm in polynomial time by using a weak random source of r bits and min-entropy $r^{\gamma}$ for any $\gamma >0$. This follows from a more general result about sampling with weak random sources. Our result matches an information-theoretic lower bound and solves a question that has been open for some years. The previous best results were a polynomial time simulation of RP [M. Saks, A. Srinivasan, and S. Zhou, Proc. 27th ACM Symp. on Theory of Computing, 1995, pp. 479--488] and a quasi-polynomial time simulation of BPP [A. Ta-Shma, Proc. 28th ACM Symp. on Theory of Computing, 1996, pp. 276--285]. Departing significantly from previous related works, we do not use extractors; instead, we use the OR-disperser of Saks, Srinivasan, and Zhou in combination with a tricky use of hitting sets borrowed from [Andreev, Clementi, and Rolim, J. ACM, 45 (1998), pp. 179--213].

We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set generators have been known as the general and uniform derandomization method for probabilistic one-sided error algorithms, while quick pseudorandom generators as the generators as the general and uniform method to derandomize probabilistic two-sided error algorithms. Our method is based on a deterministic algorithm that, given a Boolean circuit C and given access to a hitting set generator, constructs a discrepancy set for C . The main novelty is that the discrepancy set depends on C , so the new derandomization method is not uniform (i.e., not oblivious ). The algorithm works in time exponential in k(p(n)) where k (*) is the price of the hitting set generator and p (*) is a polynomial function in the size of C . We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P.

We show how to simulate any BPP algorithm in polynomial time using a weak random source of min-entropy r/sup /spl gamma// for any /spl gamma/>0. This follows from a more general result about sampling with weak random sources. Our result matches an information-theoretic lower bound and solves a question that has been open for some years. The previous best results were a polynomial time simulation of RP (Saks et al., 1995) and a n(log/sup (k)/n)-time simulation of BPP for fixed k (Ta-Shma, 1996). Departing significantly from previous related works, we do not use extractors; instead we use the OR-disperser of (Saks et al., 1995) in combination with a tricky use of hitting sets borrowed from Andreev et al. (1996). Of independent interest is our new (simplified) proof of the main result of Andreev et al., (1996). Our proof also gives some new hardness/randomness trade-offs for parallel classes.