Name
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^\gamma$, for an arbitrarily small constant $\gamma0$. 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 [B. Barak, R. Impagliazzo, and A. Wigderson, SIAM J. Comput., 36 (2006), pp. 1095-1118; B. Barak, G. Kindler, R. Shaltiel, B. Sudakov, and A. Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 1-10; R. Raz, Extractors with weak random seeds, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 11-20; J. Bourgain, Int. J. Number Theory, 1 (2005), pp. 1-32] for this problem in the sense that they do not rely on any results from arithmetic combinatorics. Using an extractor of Bourgain's [Int. J. Number Theory, 1 (2005), pp. 1-32] as a black box, we obtain a new extractor for two independent block sources with few blocks, even when the min-entropy is as small as $\operatorname{polylog}(n)$. We also show how to modify the 2 source disperser for linear min-entropy of Barak et al. [Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 1-10] and the three source extractor of Raz [Extractors with weak random seeds, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing, ACM, New York, 2005, pp. 11-20] to get dispersers/extractors with exponentially small error and linear output length where previously both were constant. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/060671218 | SIAM J. Comput. |
Keywords | Field | DocType |
new york,independent block source,annual acm symposium,weak random seed,simulating independence,ramsey graph,b. barak,polynomially small min-entropy independent,new construction,j. number theory,independent source,constant number,extractor | Discrete mathematics,Graph,Combinatorics,Arithmetic combinatorics,Theory of computing,Disperser,Extractor,Min entropy,Number theory,Mathematics,Randomness | Journal |
Volume | Issue | ISSN |
39 | 1 | 0097-5397 |
ISBN | Citations | PageRank |
1-59593-134-1 | 41 | 1.51 |
References | Authors | |
23 | 1 | |