## From Affine to Two-Source Extractors via Approximate Duality

by Eli Ben-Sasson and Noga Zewi

#### Oded's comments

This work provides a strong motivation to the study of seedless
extractors for affine sources by showing that such extractors
(with sufficiently good parameters) yield two-source extractors
with min-entropy rate below half.
The parameters of interests (for the former extractor) are
(1) min-entropy rate half,
(2) very low error (i.e., each possible output has to appear with
probability at most twice its probability under the uniform distribution),
and (3) small (e.g., constant) entropy loss rate.

Letting $E:\{0,1\}^n\to\bitset^m$ denote the extractor for affine sources
and $IP$ denote the inner produce modulo 2, two constructions that have
the form $E_2(x,y)=IP(h(x),h(y))$ are presented:
(1) $h(z)=z E(z)$,
and (2) $h$ is a 1-1 mapping to $\bitset^{n-m}$ to $E^{-1}(v_o)$,
where $v_0$ is an arbitrary value such that $|E^{-1}(v_o)| \geq 2^{n-m}$.
The analysis first shows that, for these choices of $h$,
the mapping $E_2$ is a two-source disperser;
and next that, for any $h$, if $E_2$ is a two-source disperser
then it is a two-source extractor.
The exact parameters in the latter claim depend
on a (new) Approximate Duality Conjecture.

#### The original abstract

See ECCC TR10-144.

Back to
list of Oded's choices.