Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #5 to TR15-119 | 11th February 2019 20:21

#### Explicit Two-Source Extractors and Resilient Functions

Revision #5
Accepted on: 11th February 2019 20:21
Keywords:

Abstract:

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 an independent work by Cohen.

Changes to previous version:

fixed some more typos and minor errors.

Revision #4 to TR15-119 | 14th October 2018 22:53

#### Explicit Two-Source Extractors and Resilient Functions

Revision #4
Accepted on: 14th October 2018 22:53
Keywords:

Abstract:

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 an independent work by Cohen.

Changes to previous version:

Improvements to presentation and explanations in Section 5 of previous version. Other minor changes.

Revision #3 to TR15-119 | 2nd August 2018 22:20

#### Explicit Two-Source Extractors and Resilient Functions

Revision #3
Accepted on: 2nd August 2018 22:20
Keywords:

Abstract:

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 an independent work by Cohen.

Changes to previous version:

Major revision of presentation and structure of the paper--includes more detailed explanations.

Revision #2 to TR15-119 | 20th March 2016 00:40

#### Explicit Two-Source Extractors and Resilient Functions

Revision #2
Accepted on: 20th March 2016 00:40
Keywords:

Abstract:

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.

Changes to previous version:

(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 to TR15-119 | 28th August 2015 08:05

#### Explicit Two-Source Extractors and Resilient Functions

Revision #1
Accepted on: 28th August 2015 08:05
Keywords:

Abstract:

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.

Changes to previous version:

Expanded introduction and added more explanation.

### Paper:

TR15-119 | 23rd July 2015 22:13

#### Explicit Two-Source Extractors and Resilient Functions

TR15-119
Publication: 23rd July 2015 22:20
Keywords:

Abstract:

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].

ISSN 1433-8092 | Imprint