Name
Abstract | ||
|---|---|---|
An $(n,k)$-bit-fixing source is a distribution $X$ over $\{0,1\}^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:\{0,1\}^n \rightarrow \{0,1\}^m$ which on an arbitrary $(n,k)$-bit-fixing source outputs $m$ bits that are statistically close to uniform. Recently, Kamp and Zuckerman [Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 92-101] 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 $c0$. 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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/S0097539705447049 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
deterministic extractors,bit-fixing source,annual ieee symposium,computer science,bit-fixing sources,independent seed,bit-fixing source output,deterministic bit-fixing source extractor,log n,statistical distance,general method | Discrete mathematics,Mathematics | Journal |
Volume | Issue | ISSN |
36 | 4 | 0097-5397 |
ISBN | Citations | PageRank |
0-7695-2228-9 | 35 | 1.94 |
References | Authors | |
21 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ariel Gabizon | 1 | 156 | 13.97 |
| Ran Raz | 2 | 2772 | 180.87 |
| Ronen Shaltiel | 3 | 953 | 51.62 |