Noam Ringach

Random selection is a fundamental task in fault-tolerant distributed computing where processors select a random outcome from some domain. Two special cases of this, leader election (where the processors designate a leader amongst themselves) and collective coin flipping (where the processors agree on a common random bit), have been especially widely studied. We study these problems in the full-information model, where processors communicate via a single broadcast channel, have access to private randomness, and face a computationally unbounded adversary that controls some of the processors. Despite decades of study, key gaps remain in our understanding of the trade-offs between round complexity, communication per player in each round, and adversarial resilience. We make progress by proving new lower bounds for coin flipping protocols and both new upper and lower bounds for leader election and random selection protocols. We first show that any k-round coin flipping protocol, where each of \ell players sends 1 bit per round, can be biased by O(\ell/\log^(k)(\ell)) bad players. We obtain the same lower bound (with an additional \log^(k+1)(\ell) factor in the numerator) for leader election as well. This strengthens the previous best lower bounds [RSZ, SICOMP 2002], which ruled out coin flipping protocols resilient to O(\ell / \log^(2k-1)(\ell)) bad players and leader election protocols resilient to O(\ell / \log^(2k+1)(\ell)) bad players. As a consequence, we establish that any protocol tolerating a linear fraction of corrupt players, while restricting player messages to 1 bit per round, must run for at least \log^* \ell - O(1) rounds, improving on the prior best lower bound of \frac12 \log^* \ell - \log^* \log^* \ell. We additionally show that the current best protocols that handle a linear number of corrupt players (from [RZ, JCSS 2001], [F, FOCS 1999]) are near optimal in terms of round complexity and communication per player in a round. We next initiate the study of one-round random selection protocols where each player sends 1 bit in the round. For all m \ge (\log(\ell))^2, we obtain an \emphoptimal one-round protocol: We construct a protocol that is resilient to O(\ell / m) bad players, outputting m uniform random bits. And, we show that any protocol that outputs m uniform random bits can be corrupted using O(\ell / m) bad players. As far as we are aware, this is the first provably optimal protocol for any task in the full information model. As a consequence of our construction, we obtain a one-round leader election protocol resilient to \ell / (\log(\ell))^2 bad players, improving on the previous best protocol from [RZ, JCSS 2001] that is resilient to only \ell / (\log(\ell))^3 bad players and requires players to send many bits. When m = (\log(\ell))^2, our resilience parameter matches that of the best one-round coin flipping protocol by Ajtai and Linial, which only outputs one bit. To obtain our lower bound, we introduce and study multi-output influence, a natural extension of the notion of influence of boolean functions to the multi-output setting.

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,\ell)-oNOSF source is a sequence of \ell blocks \mathbfX = (\mathbfX_1, …, \mathbfX_\ell)∼({0, 1}^n)^\ell, where at least g of the blocks are \emphgood (are independent and have some min-entropy), and the remaining \emphbad blocks are controlled by an \emphonline 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 \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). 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. 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 \emphonline influence, and believe is of independent interest. Using tools from Fourier analysis, we 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 further constructing the required leader election protocols. These extractor constructions achieve parameters that go beyond standard resilient functions [AL, Combinatorica’93].

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.