Noam Ringach

In fault-tolerant distributed computing, two fundamental tasks are collective coin flipping—where processors agree on a common random bit—and leader election—where they designate a leader among themselves. 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, which also imply lower bounds for leader election protocols. Specifically, we 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. For all k>1 this strengthens the previous best lower bounds [RSZ, SICOMP 2002], which ruled out protocols resilient to adversaries controlling O(\ell / \log^(2k-1)(\ell)) 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. This lower bound also matches the number of rounds, \log^*\ell, taken by the current best coin flipping protocols from [RZ, JCSS 2001], [F, FOCS 1999] that can handle a linear sized coalition of bad players, given the additional freedom that players can send unlimited bits per round. We also extend our techniques to derive lower bounds for protocols allowing multi-bit messages per round. Our results show that the protocols from [RZ, JCSS 2001], [F, FOCS 1999] that handle a linear number of corrupt players are almost optimal in terms of round complexity and communication per player in a round. A key technical ingredient in proving our lower bounds is a new result regarding biasing most functions from a family of functions using a common set of bad players and a small specialized set of bad players specific to each function that is biased. Complementing our lower bound results, we give improved constant-round coin flipping protocols in the setting that each player can send 1 bit per round. For example, in the case of two rounds, our protocol can handle O(\ell/ (\log \ell)(\log\log\ell)^2) sized coalition of bad players; this is better than the best one-round protocol (also called a resilient function) by [AL, Combinatorica 1993] in this setting, which can only handle O(\ell / (\log \ell)^2) sized coalition of bad players.

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.