Zero-Fixing Extractors for Sub-Logarithmic Entropy.
Gil Cohen, Igor Shinkar · Electronic colloquium on computational complexity · 2014
An (n, k)-bit-fixing source is a distribution on n bit strings, that is fixed on \(n-k\) of the coordinates, and jointly uniform on the remaining k bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract \((1-o(1)) \cdot k\) bits for \(k = \mathrm{poly}\log {n}\), almost matching the probabilistic argument. Intriguingly, unlike other well-studied sources of randomness, a result of Kamp and Zuckerman [SICOMP 2006] shows that, for any k, some small portion of the entropy in an (n, k)-bit-fixing source can be extracted. Although the extractor does not extract all the entropy, it does extract \(\log (k)/2\) bits.