Search Results

We investigate the tasks of deterministically condensing and extracting 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 in many parameter regimes [AORSV, EUROCRYPT'20]. A (g,𝓁)-oNOSF source is a sequence of 𝓁 blocks 𝐗 = (𝐗₁, … , 𝐗_{𝓁})∼ ({0, 1}ⁿ)^{𝓁}, 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 (in regimes where extraction is impossible) was recently studied in [CGR, FOCS'24]. They proved condensing impossibility results for various values of g and 𝓁, and they showed the existence of condensers matching the impossibility results in the special case when n is exponential in 𝓁 (i.e., the setting of few blocks of large length). In this work, not only do we construct the first explicit condensers matching the existential results of [CGR, FOCS'24], but we make a doubly exponential improvement by handling the case when n is only polylogarithmic in 𝓁. We also obtain a much improved explicit construction for transforming low-entropy oNOSF sources (where the good blocks only have min-entropy, as opposed to being uniform) into uniform oNOSF sources. As our next result, we essentially resolve the question of the existence of condensers for oNOSF sources by showing the existence of condensers in almost all parameter regimes, even when n is a large enough constant and 𝓁 is growing. 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. Next, we turn to understanding the possibility of extraction from oNOSF sources. For proving lower bounds, we introduce and initiate a systematic study of a new, natural notion of the influence of functions, which we call online influence, and establish tight bounds on the total online influence of functions, which imply extraction lower bounds. Lastly, we give explicit extractor constructions for oNOSF sources using novel connections to leader election protocols, and we further construct the required leader election protocols. These extractor constructions achieve parameters that go beyond the standard resilient functions of [AL, Combinatorica'93].