Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR95-058 | 20th November 1995 00:00

On Extracting Randomness From Weak Random Sources


Authors: Amnon Ta-Shma
Publication: 27th November 1995 22:21
Downloads: 1281


We deal with the problem of extracting as much randomness as possible
from a defective random source.
We devise a new tool, a ``merger'', which is a function that accepts
d strings, one of which is uniformly distributed,
and outputs a single string that is guaranteed to be uniformly
distributed. We show how to build good explicit mergers,
and how mergers can be used to build better extractors.

Previous work has succeeded in extracting ``some'' of the randomness
from sources with ``large'' min-entropy.
We improve on this in two respects. First, we build extractors
for any source, whatever its min-entropy is,
and second, we extract all the randomness in the given source.

Efficient extractors have many applications,
and we show that using our extractor we get better results in many
of these applications,
e.g., we achieve the first explicit N superconcentrators of linear
size and polyloglog(N) depth.

ISSN 1433-8092 | Imprint