Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-145 | 5th December 2005 00:00

How to get more mileage from randomness extractors


Authors: Ronen Shaltiel
Publication: 6th December 2005 17:41
Downloads: 1921


Let $\cal C$ be a class of distributions over $\B^n$. A deterministic randomness extractor for $\cal C$ is a function $E:\B^n \ar \B^m$ such that for any $X$ in $\cal C$ the distribution $E(X)$ is statistically close to the uniform distribution. A long line of research deals with explicit constructions of such extractors for various classes $\cal C$
while trying to maximize $m$.

In this paper we give a general transformation that transforms a deterministic extractor $E$ that extracts ``few'' bits into an extractor $E'$ that extracts ``almost all the bits present in the source distribution''. More precisely, we prove a general theorem saying that if $E$ and $\cal C$ satisfy certain properties, then we can transform $E$ into an extractor $E'$.

Our methods build on (and generalize) a technique of Gabizon, Raz and Shaltiel (FOCS 2004) that present such a transformation for the very restricted class $\cal C$ of ``oblivious bit-fixing sources''. Loosely speaking the high level idea is to find properties of $E$ and $\cal C$ which allow ``recycling'' the output of $E$ so that it can be ``reused'' to operate on the source distribution. An obvious obstacle is that the output of $E$ is correlated with the source distribution.

Using our transformation we give an explicit construction of a \emph{two-source extractor} $E:\B^n \times \B^n \ar \B^m$ such that for every two independent distributions $X_1$ and $X_2$ over $\B^n$ with min-entropy at least $k=(1/2+\delta)n$, $E(X_1,X_2)$ is $\eps$-close to the uniform distribution on $m=2k-C_{\delta}\log(1/\eps)$ bits. This result is optimal except for the precise constant $C_{\delta}$ and improves previous results by Chor and Goldreich (SICOMP 1988), Vazirani (Combinatorica 1987) and Dodis et al. (RANDOM 2004).

We also give explicit constructions of \emph{extractors for samplable distributions} that extract many bits even out of ``low-entropy'' samplable distributions. This improves some previous results by Trevisan and Vadhan (FOCS 2000).

ISSN 1433-8092 | Imprint