Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-058 | 16th April 2019 18:09

Extractors for small zero-fixing sources


Authors: Pavel Pudlak, Vojtech Rodl
Publication: 16th April 2019 18:10
Downloads: 81


A random variable $X$ is an $(n,k)$-zero-fixing source if for some subset $V\subseteq[n]$, $X$ is the uniform distribution on the strings $\{0,1\}^n$ that are zero on every coordinate outside of $V$. An $\epsilon$-extractor for $(n,k)$-zero-fixing sources is a mapping $F:\{0,1\}^n\to\{0,1\}^m$, for some $m$, such that $F(X)$ is $\epsilon$-close in statistical distance to the uniform distribution on $\{0,1\}^m$ for every $(n,k)$-zero-fixing source $X$. Zero-fixing sources were introduced by Cohen and Shinkar in~2015 in connection with the previously studied extractors for bit-fixing sources. They constructed, for every $\mu>0$, an efficiently computable extractor that extracts a positive fraction of entropy, i.e., $\Omega(k)$ bits, from $(n,k)$-zero-fixing sources where $k\geq(\log\log n)^{2+\mu}$.

In this paper we present two different constructions of extractors for zero-fixing sources that are able to extract a positive fraction of entropy for $k$ essentially smaller than $\log\log n$. The first extractor works for $k\geq C\log\log\log n$, for some constant $C$. The second extractor extracts a positive fraction of entropy for $k\geq \log^{(i)}n$ for any fixed $i\in \N$, where $\log^{(i)}$ denotes $i$-times iterated logarithm. The fraction of extracted entropy decreases with $i$. The first extractor is a function computable in polynomial time in~$n$ (for $\epsilon=o(1)$, but not too small); the second one is computable in polynomial time when $k\leq\alpha\log\log n/\log\log\log n$, where $\alpha$ is a positive constant.

ISSN 1433-8092 | Imprint