Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-011 | 7th April 1997 00:00

Weak Random Sources, Hitting Sets, and BPP Simulations



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.

ISSN 1433-8092 | Imprint