Title: 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)γ.
Publication Year: 2006
Publication Date: 2006-05-21
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 68
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot