Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR15-125 | 11th June 2017 23:46

Improved Constructions of Two-Source Extractors

RSS-Feed




Revision #2
Authors: Xin Li
Accepted on: 11th June 2017 23:46
Downloads: 42
Keywords: 


Abstract:

In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy $k \geq \log^C n$ for some large enough constant $C$, where $n$ is the length of the source. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to $k^{\Omega(1)}$, while the error remains $n^{-\Omega(1)}$ and the extractor remains strong in the second source. In the non-strong case, the output can be increased to $k$. Our improvement is obtained by giving a better extractor for $(q, t, \gamma)$ non-oblivious bit-fixing sources, which can output $t^{\Omega(1)}$ bits instead of one bit as in \cite{CZ15}.

We also give the first explicit construction of deterministic extractors for affine sources over $F_2$, with entropy $k \geq \log^C n$ for some large enough constant $C$, where $n$ is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require the affine source to have entropy at least $\Omega(n/\sqrt{\log \log n})$. Our extractor outputs $k^{\Omega(1)}$ bits with error $n^{-\Omega(1)}$. This is done by reducing an affine source to a non-oblivious bit-fixing source, where we adapt the alternating extraction based approach in previous work on independent source extractors \cite{Li13b} to the affine setting. Our affine extractors also imply improved extractors for circuit sources studied in \cite{Viola11}.

We further extend our results to the case of zero-error dispersers, and give two applications in data structures that rely crucially on the fact that our two-source or affine extractors have large output size.



Changes to previous version:

Extend the results to the case of zero-error dispersers, and give two applications in data structures.


Revision #1 to TR15-125 | 3rd February 2016 00:30

Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy





Revision #1
Authors: Xin Li
Accepted on: 3rd February 2016 00:30
Downloads: 970
Keywords: 


Abstract:

In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy $k \geq \log^C n$ for some large enough constant $C$, where $n$ is the length of the source. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to $k^{\Omega(1)}$, while the error remains $n^{-\Omega(1)}$ and the extractor remains strong in the second source. In the non-strong case, the output can be increased to $k$.\ Our improvement is obtained by giving a better extractor for $(q, t, \gamma)$ non-oblivious bit-fixing sources, which can output $t^{\Omega(1)}$ bits instead of one bit as in \cite{CZ15}.

We also give the first explicit construction of deterministic extractors for affine sources over $\F_2$, with entropy $k \geq \log^C n$ for some large enough constant $C$, where $n$ is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require the affine source to have entropy at least $\Omega(n/\sqrt{\log \log n})$. Our extractor outputs $k^{\Omega(1)}$ bits with error $n^{-\Omega(1)}$. This is done by reducing an affine source to a non-oblivious bit-fixing source, where we adapt the alternating extraction based approach in previous work on independent source extractors \cite{Li13b} to the affine setting. Our affine extractors also imply improved extractors for circuit sources studied in \cite{Viola11}.



Changes to previous version:

Corrected some typos and references, added some results, and merged with TR15-121.


Paper:

TR15-125 | 5th August 2015 17:56

Improved Constructions of Two-Source Extractors





TR15-125
Authors: Xin Li
Publication: 6th August 2015 14:08
Downloads: 647
Keywords: 


Abstract:

In a recent breakthrough \cite{CZ15}, Chattopadhyay and Zuckerman gave an explicit two-source extractor for min-entropy $k \geq \log^C n$ for some large enough constant $C$. However, their extractor only outputs one bit. In this paper, we improve the output of the two-source extractor to $k^{\Omega(1)}$, while the error remains $n^{-\Omega(1)}$.

Our improvement is obtained by giving a better extractor for $(q, t, \gamma)$ non-oblivious bit-fixing sources, which can output $t^{\Omega(1)}$ bits instead of one bit as in \cite{CZ15}.



ISSN 1433-8092 | Imprint