Extractors for a constant number of polynomially small min-entropy independent sources

Abstract

We consider the problem of randomness extraction from independent sources. We construct an extractor that can extract from a constant number of independent sources of length n, each of which have min-entropy nγ for an arbitrarily small constant γ > 0. Our extractor is obtained by composing seeded extractors in simple ways. We introduce a new technique to condense independent somewhere-random sources which looks like a useful way to manipulate independent sources. Our techniques are different from those used in recent work [1, 2, 16, 5] for this problem in the sense that they do not rely on any results from additive number theory.Using Bourgain's extractor [5] as a black box, we obtain a new extractor for 2 independent block-sources with few blocks, even when the min-entropy is as small as polylog(n). We also show how to modify the 2 source disperser for linear min-entropy of Barak et al. [2] and the 3 source extractor of Raz [16] to get dispersers/extractors with exponentially small error and linear output length where previously both were constant.In terms of Ramsey Hypergraphs, for every constant 1> γ >0 our construction gives a family of explicit O(1/γ)-uniform hypergraphs on N vertices that avoid cliques and independent sets of size 2(log N)γ.