We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective random sources for which it is known that extraction is impossible [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks $\mathbf{X} = (\mathbf{X}_1, \dots, \mathbf{X}_{\ell})\sim (\{0, 1\}^{n})^{\ell}$, where at least $g$ of the blocks are good (are independent and have some min-entropy), and the remaining bad blocks are controlled by an online adversary where each bad block can be arbitrarily correlated with any block that appears before it.
The existence of condensers was recently studied in [CGR, FOCS'24]. They proved condensing impossibility results for various values of $g$ and $\ell$, and they showed the existence of condensers matching the impossibility results in the special case when $n$ is extremely large compared to $\ell$ (i.e., the setting of few blocks of large length).
In this work, we make significant progress on proving the existence of condensers with strong parameters in almost all parameter regimes, even when $n$ is a large enough constant and $\ell$ is growing. This almost resolves the question of the existence of condensers for oNOSF sources, except when $n$ is a small constant.
As our next result, we construct the first explicit condensers for oNOSF sources and achieve parameters that match the existential results of [CGR, FOCS'24]. We also obtain a much improved construction for transforming low-entropy oNOSF sources (where the good blocks only have min-entropy, as opposed to being uniform) into uniform oNOSF sources.
We find interesting connections and applications of our results on condensers to collective coin flipping and collective sampling, problems that are well-studied in fault-tolerant distributed computing. We use our condensers to provide very simple protocols for these problems.
Finally, to understand the case of small $n$, we focus on $n=1$ which corresponds to online non-oblivious bit-fixing (oNOBF) sources. We introduce and initiate a systematic study of a new, natural notion of the influence of Boolean functions, which we call online influence, and believe is of independent interest. Using tools from Boolean Fourier analysis, we establish tight bounds on the total online influence of Boolean functions, which imply extraction lower bounds. Several problems remain open regarding this new measure of influence; progress on these will lead to improved extractors and condensers for oNOBF sources or further strengthen our lower bounds.
