On the Existence of Seedless Condensers: Exploring the Terrain

While the existence of randomness extractors, both seeded and seedless, has been studied for many sources of randomness, currently, not much is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources (originally defined as SHELA sources in [1]), and almost Chor-Goldreich (CG) sources as defined in [2]. We will think of these sources as a sequence of random variables <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{X}=\mathbf{X}_{1}, \ldots,\mathbf{X}_{\ell}$</tex> on <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell$</tex> symbols where at least <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$g$</tex> out of these <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell$</tex> symbols are “good” (i.e., have some min-entropy requirement), denoted as a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(g, \ell)-\mathbf{source}$</tex>, and the remaining “bad” <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell-g$</tex> symbols may adversarially depend on these <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$g$</tex> good blocks. The difference between each of these sources is realized by restrictions on the power of the adversary, with the adversary in NOSF sources having no restrictions. Prior to our work, the only known seedless condenser upper or lower bound in these settings is due to [2], where they explicitly construct a seedless condenser for a restricted subset of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(g,\ell)- \mathbf{adversarial}$</tex> CG sources. The following are our main results concerning seedless condensers for each of these sources. 1) oNOSF sources a) When <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$g\leq\ell/2$</tex>, we prove that condensing with error 0.99 above rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\frac{1}{\lfloor\ell/g\rfloor}$</tex> is impossible. In fact, we show that this is tight. b) Quite surprisingly, for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$g &gt; \ell/2$</tex>, we show the existence of excellent condensers for uniform oNOSF sources. In addition, we show the existence of similar condensers for oNOSF sources with only logarithmic min-entropy. Our results are based on a new type of two-source extractors, called output-light two-source extractors, that we introduce and prove the existence of. 2) Adversarial CG sources a) We observe that uniform adversarial CG sources are equivalent to uniform oNOSF sources and consequently inherit the same results. b) We show that one cannot condense beyond the min-entropy gap of each block or condense low min-entropy CG sources above rate 1/2. 3) NOSF sources a) We show that condensing with constant error above rate <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\frac{g}{\ell}$</tex> is impossible for uniform NOSF sources for any <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$g$</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\ell$</tex>, thus ruling out the possibility of any non-trivial condensing. This shows an interesting distinction between NOSF and oNOSF sources.