ECCC-Report TR15-119https://eccc.weizmann.ac.il/report/2015/119Comments and Revisions published for TR15-119en-usMon, 11 Feb 2019 20:21:20 +0200
Revision 5
| Explicit Two-Source Extractors and Resilient Functions |
Eshan Chattopadhyay,
David Zuckerman
https://eccc.weizmann.ac.il/report/2015/119#revision5We 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.Mon, 11 Feb 2019 20:21:20 +0200https://eccc.weizmann.ac.il/report/2015/119#revision5
Revision 4
| Explicit Two-Source Extractors and Resilient Functions |
Eshan Chattopadhyay,
David Zuckerman
https://eccc.weizmann.ac.il/report/2015/119#revision4We 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.
Sun, 14 Oct 2018 22:53:04 +0300https://eccc.weizmann.ac.il/report/2015/119#revision4
Revision 3
| Explicit Two-Source Extractors and Resilient Functions |
Eshan Chattopadhyay,
David Zuckerman
https://eccc.weizmann.ac.il/report/2015/119#revision3We 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.Thu, 02 Aug 2018 22:20:10 +0300https://eccc.weizmann.ac.il/report/2015/119#revision3
Revision 2
| Explicit Two-Source Extractors and Resilient Functions |
Eshan Chattopadhyay,
David Zuckerman
https://eccc.weizmann.ac.il/report/2015/119#revision2We 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.
Sun, 20 Mar 2016 00:40:06 +0200https://eccc.weizmann.ac.il/report/2015/119#revision2
Revision 1
| Explicit Two-Source Extractors and Resilient Functions |
Eshan Chattopadhyay,
David Zuckerman
https://eccc.weizmann.ac.il/report/2015/119#revision1We 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.Fri, 28 Aug 2015 08:05:57 +0300https://eccc.weizmann.ac.il/report/2015/119#revision1
Paper TR15-119
| Explicit Two-Source Extractors and Resilient Functions |
Eshan Chattopadhyay,
David Zuckerman
https://eccc.weizmann.ac.il/report/2015/119We 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].Thu, 23 Jul 2015 22:20:50 +0300https://eccc.weizmann.ac.il/report/2015/119