Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR97-011 | 7th April 1997 00:00

#### Weak Random Sources, Hitting Sets, and BPP Simulations

TR97-011
Authors: Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan
Publication: 11th April 1997 18:44
Keywords:

Abstract:

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