Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOSE' D.P. ROLIM AND TREVISAN:
All reports by Author Jose' D.P. Rolim and Trevisan:

TR97-011 | 7th April 1997
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan

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 ... more >>>




ISSN 1433-8092 | Imprint