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.
Extend the results to the case of zero-error dispersers, and give two applications in data structures.
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}.
Corrected some typos and references, added some results, and merged with TR15-121.
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}.
