Alexander E. Andreev, Andrea E.F. Clementi, Jose D.P. Rolim, and Luca Trevisan.
Weak Random Sources, Hitting Sets, and BPP Simulations.
ECCC TR 97-11.
Submitted, April 1997.
We show how to simulate any BPP algorithm in polynomial time using a weak random source of 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, by Sacks et al. (1995), and a $n^{\log^{(k)} n}$-time simulation of BPP for fixed $k$, by Ta-Shma (1996).

Departing significantly from previous related works, we do not use extractors; instead, we use OR-dispersers in combination with a tricky use of hitting sets borrowed from a paper of Andreev et al. (1996).

Of independent interest is our new (simplified) proof of the main result of Andreev et al. (1996). Our proof also yields some new hardness/randomness trade-offs for parallel classes.