期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1995
卷号：1995
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
