On extracting randomness from weak random sources (extended abstract)
Amnon Ta‐Shma · 1996
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.