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.