Extracting Randomness: A Survey and New Constructions

摘要

Extractors are Boolean functions that allow, in some precise sense, extraction of randomness from somewhat random distributions, using only a small amount of truly random bits. Extractors, and the closely related “dispersers,” exhibit some of the most “random-like” properties of explicitly constructed combinatorial structures. In this paper we do two things. First, we survey extractors and dispersers: what they are, how they can be designed, and some of their applications. The work described in the survey is due to a long list of research papers by various authors—most notably by David Zuckerman. Then, we present a new tool for constructing explicit extractors and give two new constructions that greatly improve upon previous results. The new tool we devise, a “merger,” is a function that acceptsdstrings, 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. Using this, we present two new constructions. The first construction succeeds in extractingallof the randomness fromanysomewhat random source. This improves upon previous extractors that extract onlysomeof the randomness from somewhat random sources with “enough” randomness. The amount of truly random bits used by this extractor, however, is not optimal. The second extractor we build extracts only some of the randomness and works only for sources with enough randomness, but uses a near-optimal amount of truly random bits. Extractors and dispersers have many applications in “removing randomness” in various settings and in making randomized constructions explicit. We survey some of these applications and note whenever our new constructions yield better results, e.g., plugging our new extractors into a previous construction we achieve the first explicitN-superconcentrators of linear size and polyloglog(N) depth.