Lossless condensers, unbalanced expanders, and extractors (Q2460624)

An extractor is a function that is given an input from a source having certain min-entropy and a number of truly random bits (seed) independent of the source and outputs a number of bits with a probability distribution that is statistically close to the uniform distribution. Previous results had achieved a number of output bits roughly the sum of the min-entropy of the source plus the length of the seed, and a seed length logarithmic in the length of the source; however the used techniques only work if the min-entropy is at least a constant power of the length of the source, for smaller min-entropies a seed of length up to the square of the logarithm in the length of the source. This paper presents a method for obtaining an extractor that works for all min-entropies, given an extractor that works for high min-entropy. Furthermore, the extractor does not lose entropy. Applications include the construction of dispersers (certain ``one-sided extractors'') with low entropy loss, almost optimal super-concentrators of depth 2, and a new method for constructing unbalanced expander graphs with small degree.