TR97-011 Authors: Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan

Publication: 11th April 1997 18:44

Downloads: 2234

Keywords:

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 and

solves a question that has been open for some years.

The previous best results were a polynomial

time simulation of RP \cite{SSZ95} and a $n^{\log^{(k)} n}$-time

simulation of BPP, for fixed $k$~\cite{T96}.

Departing significantly from previous related works, we do not

use extractors; instead, we use the

OR-disperser of~\cite{SSZ95} in combination with a tricky

use of hitting sets borrowed from~\cite{ACR96}.

Of independent interest is our new (simplified) proof

of the main result of~\cite{ACR96}. Our proof also

gives some new hardness/randomness trade-offs for

parallel classes.