ECCC-Report TR05-109https://eccc.weizmann.ac.il/report/2005/109Comments and Revisions published for TR05-109en-usThu, 29 Sep 2005 19:21:58 +0300
Paper TR05-109
| Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed |
Ariel Gabizon,
Ran Raz,
Ronen Shaltiel
https://eccc.weizmann.ac.il/report/2005/109An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that
there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly
distributed and independent of each other, and the remaining $n-k$ variables
are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n
\ar \B^m$ which on an arbitrary $(n,k)$-bit-fixing source outputs $m$ bits that
are statistically-close to uniform. Recently, Kamp and Zuckerman [44th FOCS,
2003] gave a construction of a deterministic bit-fixing source extractor that
extracts $\Omega(k^2/n)$ bits and requires $k>\sqrt{n}$.
In this paper we give constructions of deterministic bit-fixing
source extractors that extract $(1-o(1))k$ bits whenever $k>(\log
n)^c$ for some universal constant $c>0$. Thus, our constructions
extract almost all the randomness from bit-fixing sources and work
even when $k$ is small. For $k \gg \sqrt{n}$ the extracted bits
have statistical distance $2^{-n^{\Omega(1)}}$ from uniform, and
for $k \le \sqrt{n}$ the extracted bits have statistical distance
$k^{-\Omega(1)}$ from uniform.
Our technique gives a general method to transform deterministic
bit-fixing source extractors that extract few bits into extractors
which extract almost all the bits.
Thu, 29 Sep 2005 19:21:58 +0300https://eccc.weizmann.ac.il/report/2005/109