Extractors for small zero-fixing sources (Q2095117)

Let \(V \subseteq [n]\) be a \(k\)-element subset of \([n]\). The uniform distribution on the \(2^{k}\) strings from \(\{0,1\}^{n}\) that are set to zero outside of \( V\) is called an \((n, k)\)-zero-fixing source. An \(\epsilon\)-extractor for \((n, k)\)-zero-fixing sources is a mapping \(F : \{0,1\}^{n}\rightarrow \{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 \textit{G. Cohen} and \textit{I. Shinkar} [Lect. Notes Comput. Sci. 9134, 343--354 (2015; Zbl 1441.68036)] in connection with the previously studied extractors for bit-fixing sources.\par In this paper, the authors present two different constructions of extractors for zero-fixing sources that are able to extract a positive fraction of entropy for \(k\) substantially 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 \mathbb{N}\), where \(\log^{(i)}\) denotes \(i\)-times iterated logarithm. The first extractor is a function computable in polynomial time in \(n\); the second one is computable in polynomial time in \(n\) when \( k\leq \alpha \log\log n/\log\log\log n\), where \(\alpha\) is a positive constant. These results can also be viewed as lower bounds on some Ramsey-type properties. The main difference between the problems about extractors studied here and the standard Ramsey theory is that in this paper the authors study colorings of all subsets of size up to \(k\) while in Ramsey theory the sizes are fixed to \(k\). However it is not difficult to derive results also for coloring of subsets of sizes equal to \(k\). The paper finishes with conclusions and open problems.