Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-058 | 20th November 1995 00:00

On Extracting Randomness From Weak Random Sources

RSS-Feed




TR95-058
Authors: Amnon Ta-Shma
Publication: 27th November 1995 22:21
Downloads: 3857
Keywords: 


Abstract:

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