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$\mathbf{X}=\mathbf{X}_{1}, \ldots,\mathbf{X}_{\ell}$on$\ell$symbols where at least$g$out of these$\ell$symbols are “good” (i.e., have some min-entropy requirement), denoted as a$(g, \ell)-\mathbf{source}$, and the remaining “bad”$\ell-g$symbols may adversarially depend on these$g$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$(g,\ell)- \mathbf{adversarial}$CG sources. The following are our main results concerning seedless condensers for each of these sources. 1) oNOSF sources a) When$g\leq\ell/2$, we prove that condensing with error 0.99 above rate$\frac{1}{\lfloor\ell/g\rfloor}$is impossible. In fact, we show that this is tight. b) Quite surprisingly, for$g > \ell/2$, 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$\frac{g}{\ell}$is impossible for uniform NOSF sources for any$g$and$\ell$, thus ruling out the possibility of any non-trivial condensing. This shows an interesting distinction between NOSF and oNOSF sources.