Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Weak Random Sources:
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 >>>

TR05-100 | 30th August 2005
David Zuckerman

Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number

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

ISSN 1433-8092 | Imprint