Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan

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 {\em sampling\/}

with weak random sources.

Our result matches an information-theoretic lower bound ...
more >>>

David Zuckerman

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. We further construct dispersers, which are similar to one-sided extractors, ... more >>>