ECCC-Report TR05-106https://eccc.weizmann.ac.il/report/2005/106Comments and Revisions published for TR05-106en-usMon, 05 Dec 2005 00:00:00 +0200
Revision 1
| Extractors for a Constant Number of Polynomial Small Min-Entropy Independent Sources |
Anup Rao
https://eccc.weizmann.ac.il/report/2005/106#revision1We 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 $\gamma >
0$. Our result is different from recent work for this problem in the sense that it does not rely on any results from additive number theory. Our extractor is built by composing previous constructions of strong
seeded extractors in simple ways.
Using Bourgain's extractor as a black box, we obtain
a new extractor for 2 independent blockwise 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. and the 3 source extractor of Raz 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> \gamma >0$ our
construction gives a family of explicit $O(1/\gamma)$-uniform
hypergraphs on $N$ vertices that avoid cliques and independent sets of
size $2^{(\log N)^\gamma}$.
Mon, 05 Dec 2005 00:00:00 +0200https://eccc.weizmann.ac.il/report/2005/106#revision1
Paper TR05-106
| Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources |
Anup Rao
https://eccc.weizmann.ac.il/report/2005/106
We consider the problem of bit 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 $\gamma > 0$. Our
constructions are different from recent extractor constructions
\cite{BarakIW04, BarakKSSW05, Raz05, Bourgain05} for this problem in
the sense that they do not rely on any results from additive number
theory. They are obtained by composing previous constructions of
strong seeded extractors in simple ways.
Wed, 28 Sep 2005 15:13:48 +0300https://eccc.weizmann.ac.il/report/2005/106