Revision #2 Authors: Eshan Chattopadhyay, David Zuckerman

Accepted on: 20th March 2016 00:40

Downloads: 21416

Keywords:

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant~$C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $\polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola, achieved $q=n^{1/2 - \delta}$.

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices,

improving bounds obtained by Barak et al. and matching independent work by Cohen.

(1) a more detailed sketch of our 2-source extractor in the introduction (Section 1.2). (2) added Theorem 2, which gives 2-source extractors for arbitrary error, at expense of more running time. (Proof sketch of this is given in Section 7). (3) various other minor edits.

Revision #1 Authors: Eshan Chattopadhyay, David Zuckerman

Accepted on: 28th August 2015 08:05

Downloads: 1823

Keywords:

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant~$C$.

Our extractor outputs one bit and has error $n^{-\Omega(1)}$.

The best previous extractor, by Bourgain, required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$.

In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown

$n-q$ bits are chosen almost $\polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits.

The best previous construction, by Viola, achieved $q=n^{1/2 - \delta}$.

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices,

improving bounds obtained by Barak et al.\ and matching independent work by Cohen.

Expanded introduction and added more explanation.

TR15-119 Authors: Eshan Chattopadhyay, David Zuckerman

Publication: 23rd July 2015 22:20

Downloads: 3582

Keywords:

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy $.499n$.

A key ingredient in our construction is an explicit construction of a monotone, almost-balanced boolean function on $n$ bits that is resilient to coalitions of size $n^{1-\delta}$, for any $\delta>0$. In fact, our construction is stronger in that it gives an explicit extractor for a generalization of non-oblivious bit-fixing sources on $n$ bits, where some unknown $n-q$ bits are chosen almost $polylog(n)$-wise independently, and the remaining $q=n^{1-\delta}$ bits are chosen by an adversary as an arbitrary function of the $n-q$ bits. The best previous construction, by Viola \cite{Viola14}, achieved $q=n^{1/2 - \delta}$.

Our other main contribution is a reduction showing how such a resilient function gives a two-source extractor. This relies heavily on the new non-malleable extractor of Chattopadhyay, Goyal and Li [CGL15].

Our explicit two-source extractor directly implies an explicit construction of a $2^{(\log \log N)^{O(1)}}$-Ramsey graph over $N$ vertices,

improving bounds obtained by Barak et al. [BRSW12] and matching independent work by Cohen [Coh15b].