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 [AORSV, EUROCRYPT'20]), and almost Chor-Goldreich (CG) sources as defined in [DMOZ, STOC'23]. We will think of these sources as a sequence of random variables $\mathbf{X}=\mathbf{X}_1,\dots,\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)$-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 [DMOZ, STOC'23], where they explicitly construct a seedless condenser for a restricted subset of $(g,\ell)$-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.

These results make progress on several open question from [DMOZ, STOC'23], [AORSV, EUROCRYPT'20], and [KN, RANDOM'23].

Improvements to main result and minor revisions to presentation

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, one-sided NOSF (oNOSF) sources (originally defined as SHELA sources in [AORSV, EUROCRYPT'20]), and almost Chor-Goldreich (CG) sources as defined in [DMOZ, STOC'23]. Here, we will think of these sources as a sequence of random variables $\mathbf{X}=\mathbf{X}_1,\dots,\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)$-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 [DMOZ, STOC'23], where they explicitly construct a seedless condenser for a restricted subset of $(g,\ell)$-adversarial CG sources.

The following are our main results concerning seedless condensers for each of these three sources.
* oNOSF sources
- 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.
- 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 \emph{output-light two-source extractors}, that we introduce and prove the existence of.
* Adversarial CG sources
- We observe that uniform adversarial CG sources are equivalent to uniform oNOSF sources and consequently inherit the same results.
- 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$.
* NOSF sources
- 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 sources and oNOSF sources.

Major additions to results and revisions to presentation.

While the existence of randomness extractors, both seeded and seedless, has been thoroughly studied for many sources of randomness, currently, very little 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, SHELA sources as defined by Aggarwal, Obremski, Ribeiro, Siniscalchi, and Visconti [AORSV, EUROCRYPT'20], and almost Chor-Goldreich (CG) sources as defined by Doron, Moshkovitz, Oh, and Zuckerman [DMOZ, STOC'23]. Here, we will think of these sources as a sequence of random variables $\mathbf{X}=\mathbf{X}_1,\dots,\mathbf{X}_\ell$ on $\ell$ symbols where at least $g$ out of these $\ell$ symbols are "good" (i.e., uniformly random), denoted as a $(g,\ell)$-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 [DMOZ, STOC'23] which explicitly constructs a seedless condenser for a restricted subset of $(g,\ell)$-almost CG sources.

The following are our main results concerning seedless condensers for each of these three sources.
1. When $g\leq\ell/2$, we prove for all three classes of sources that condensing with error 0.99 above rate $\frac{1}{\lfloor \ell/g \rfloor}$ is impossible.
2. Next, we investigate the setting of $g> \ell/2$, and in particular focus on $g=2$ and $\ell=3$. We show that condensing with constant error above rate $\frac{2}{3}$ is impossible for uniform NOSF sources.
3. Quite surprisingly, we show the existence of excellent condensers for uniform $(2,3)$-SHELA and uniform almost CG sources, thus proving a separation from NOSF sources. Further, we explicitly construct a condenser that outputs $m = \frac{n}{16}$ bits and condenses any uniform $(2,3)$-SHELA source to entropy $m - O(\log(m / \varepsilon))$ (with error $\varepsilon$). Our construction is based on a new type of seeded extractor that we call output-light, which could be of independent interest.
In contrast, we show that it is impossible to extract from uniform $(2,3)$-SHELA sources.

These results extend seedless extractor lower bounds on NOSF sources (Bourgain, Kahn, Kalai, Katznelson, and Linial [BKKKL, Israel J. Math'92]) and make progress on several open question from [DMOZ, STOC'23], [AORSV, EUROCRYPT'20], and Kopparty and N [KN, RANDOM'23].