publications

2024

1. arXiv

   Condensing Against Online Adversaries

   Eshan Chattopadhyay, Mohit Gurumukhani, and Noam Ringach

   2024

   Abs arXiv Bib HTML PDF

   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.

   @misc{chattopadhyay2024condensingonlineadversaries,
     title = {Condensing Against Online Adversaries},
     author = {Chattopadhyay, Eshan and Gurumukhani, Mohit and Ringach, Noam},
     year = {2024},
     eprint = {2411.04115},
     archiveprefix = {arXiv},
     primaryclass = {cs.CC},
     url = {https://arxiv.org/abs/2411.04115},
   }

2. arXiv

   Two-Sided Lossless Expanders in the Unbalanced Setting

   Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Yunya Zhao

   2024

   ISSN: 1433-8092

   Abs arXiv Bib HTML PDF

   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.

   @misc{chattopadhyay2024twosidedlosslessexpandersunbalanced,
     title = {Two-Sided Lossless Expanders in the Unbalanced Setting},
     author = {Chattopadhyay, Eshan and Gurumukhani, Mohit and Ringach, Noam and Zhao, Yunya},
     year = {2024},
     eprint = {2409.04549},
     archiveprefix = {arXiv},
     primaryclass = {cs.CC},
     url = {https://arxiv.org/abs/2409.04549},
     note = {ISSN: 1433-8092},
   }

3. FOCS24

   On the Existence of Seedless Condensers: Exploring the Terrain

   Eshan Chattopadhyay, Mohit Gurumukhani, and Noam Ringach

   In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) , 2024

   Abs arXiv Bib HTML PDF

   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.

   @inproceedings{chattopadhyay2024existenceseedlesscondensersexploring,
     title = {On the Existence of Seedless Condensers: Exploring the Terrain},
     author = {Chattopadhyay, Eshan and Gurumukhani, Mohit and Ringach, Noam},
     booktitle = {2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)},
     year = {2024},
     volume = {},
     number = {},
     archiveprefix = {arXiv},
     primaryclass = {cs.CC},
     url = {https://arxiv.org/abs/2312.15087},
     keywords = {Computer science;Randomness Condensers;Expanders; Lossless Expanders; Pseudorandomness},
     eprint = {2312.15087},
   }

2020

1. Science

   Cerebellar nuclei evolved by repeatedly duplicating a conserved cell-type set

   Justus M. Kebschull, Ethan B. Richman, Noam Ringach, Drew Friedmann , and 12 more authors

   Science, 2020

   Abs Bib HTML PDF

   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.

   @article{kebschull2020cerebellarnuclei,
     author = {Kebschull, Justus M. and Richman, Ethan B. and Ringach, Noam and Friedmann, Drew and Albarran, Eddy and Kolluru, Sai Saroja and Jones, Robert C. and Allen, William E. and Wang, Ying and Cho, Seung Woo and Zhou, Huaijun and Ding, Jun B. and Chang, Howard Y. and Deisseroth, Karl and Quake, Stephen R. and Luo, Liqun},
     title = {Cerebellar nuclei evolved by repeatedly duplicating a conserved cell-type set},
     journal = {Science},
     volume = {370},
     number = {6523},
     pages = {eabd5059},
     year = {2020},
     doi = {10.1126/science.abd5059},
     url = {https://www.science.org/doi/abs/10.1126/science.abd5059},
     eprint = {https://www.science.org/doi/pdf/10.1126/science.abd5059},
   }