ECCC-Report TR05-145https://eccc.weizmann.ac.il/report/2005/145Comments and Revisions published for TR05-145en-usTue, 06 Dec 2005 17:41:50 +0200
Paper TR05-145
| How to get more mileage from randomness extractors |
Ronen Shaltiel
https://eccc.weizmann.ac.il/report/2005/145Let $\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).
Tue, 06 Dec 2005 17:41:50 +0200https://eccc.weizmann.ac.il/report/2005/145