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