Improved Constructions of Two-Source Extractors

by Xin Li

Oded's comments

Seems that this research direction is ultra vibrant (after being stuck for years - see 020). Here is a third posting in a row (following 180 and 181). It addresses one of the two open problems with which I ended the previous posting.

The original 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}.

See ECCC TR15-125.


Back to list of Oded's choices.