ECCC-Report TR95-058https://eccc.weizmann.ac.il/report/1995/058Comments and Revisions published for TR95-058en-usMon, 27 Nov 1995 22:21:49 +0200
Paper TR95-058
| On Extracting Randomness From Weak Random Sources |
Amnon Ta-Shma
https://eccc.weizmann.ac.il/report/1995/058We 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.
Mon, 27 Nov 1995 22:21:49 +0200https://eccc.weizmann.ac.il/report/1995/058