Noam Ringach

We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model for which extraction is impossible [AORSV, EUROCRYPT’20]. A (g,ℓ)-oNOSF source is a sequence of ℓ blocks where at least g of the blocks are good (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 studied in [CGR, FOCS’24]. They proved condensing impossibility results for various values of g,ℓ and showed the existence of condensers matching the impossibility results in the case when n is extremely large compared to ℓ. 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 ℓ is growing. This almost resolves the question of the existence of condensers for oNOSF sources, except when n is a small constant. We construct the first explicit condensers for oNOSF sources, achieve parameters that match the existential results of [CGR, FOCS’24], and obtain an improved construction for transforming low-entropy oNOSF sources into uniform ones. We find applications of our results to collective coin flipping and sampling, well-studied problems in fault-tolerant distributed computing. We use our condensers to provide simple protocols for these problems. To understand the case of small n, we focus on n=1 which corresponds to online non-oblivious bit-fixing (oNOBF) sources. We initiate a study of a new, natural notion of influence of Boolean functions which we call online influence. We establish tight bounds on the total online influence of Boolean functions, implying extraction lower bounds.

We present the first explicit construction of two-sided lossless expanders in the unbalanced setting (bipartite graphs that have many more nodes on the left than on the right). Prior to our work, all known explicit constructions in the unbalanced setting achieved only one-sided lossless expansion. Specifically, we show that the one-sided lossless expanders constructed by Kalev and Ta-Shma (RANDOM’22)–that are based on multiplicity codes introduced by Kopparty, Saraf, and Yekhanin (STOC’11)–are, in fact, two-sided lossless expanders. Using our unbalanced bipartite expander, we easily obtain lossless (non-bipartite) expander graphs on N vertices with polynomial degree and a free group action. As far as we know, this is the first explicit construction of lossless (non-bipartite) expanders with N vertices and degree ≪N.

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 [AORSV, EUROCRYPT’20], and adversarial Chor-Goldreich (aCG) source [DMOZ, STOC’23]. We think of these sources as a sequence of random variables X=X1,…,Xℓ on ℓ symbols where at least g out of these ℓ symbols are "good" (i.e., have some min-entropy requirement), denoted as a (g,ℓ)-source, and the remaining "bad" ℓ−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. 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,ℓ)-aCG sources. We show: 1) oNOSF sources a) When g≤ℓ/2, we prove that condensing with error 0.99 above rate 1⌊ℓ/g⌋ is impossible. In fact, we show that this is tight. b) For g>ℓ/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. 2) aCG sources a) We observe that uniform aCG 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 gℓ is impossible for uniform NOSF sources for any g and ℓ, thus ruling out the possibility of any non-trivial condensing. This shows a distinction between NOSF sources and oNOSF sources.

Cerebellar nuclei, substructures of the cerebellum, transfer information from the cerebellum to other parts of the brain. Using single-cell transcriptomics, Kebschull et al. have now identified a conserved pattern of cerebellar nuclei structure that has been repeated through evolution (see the Perspective by Hatten). Ranging from mice to chickens to humans, cerebellar nuclei are made up of region-specific excitatory neurons and region-invariant inhibitory neurons. In humans, a facet connecting the cerebellum to the frontal cortex is enhanced. Science, this issue p. eabd5059; see also p. 1411 Evolutionary duplication and divergence of a conserved cell type set account for the expansion of the brain’s cerebellar nuclei. How have complex brains evolved from simple circuits? Here we investigated brain region evolution at cell-type resolution in the cerebellar nuclei, the output structures of the cerebellum. Using single-nucleus RNA sequencing in mice, chickens, and humans, as well as STARmap spatial transcriptomic analysis and whole–central nervous system projection tracing, we identified a conserved cell-type set containing two region-specific excitatory neuron classes and three region-invariant inhibitory neuron classes. This set constitutes an archetypal cerebellar nucleus that was repeatedly duplicated to form new regions. The excitatory cell class that preferentially funnels information to lateral frontal cortices in mice becomes predominant in the massively expanded human lateral nucleus. Our data suggest a model of brain region evolution by duplication and divergence of entire cell-type sets.