Search Results

Documents authored by Ringach, Noam

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.34
Two-Sided Lossless Expanders in the Unbalanced Setting

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

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
We present the first explicit construction of two-sided lossless expanders in the unbalanced setting (bipartite graphs that have polynomially 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. Moreover, we show that our result is tight, thus completely characterizing the graph of Kalev and Ta-Shma.
Cite as

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Yunya Zhao. Two-Sided Lossless Expanders in the Unbalanced Setting. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 34:1-34:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.APPROX/RANDOM.2026.34,
  author =	{Chattopadhyay, Eshan and Gurumukhani, Mohit and Ringach, Noam and Zhao, Yunya},
  title =	{{Two-Sided Lossless Expanders in the Unbalanced Setting}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{34:1--34:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.34},
  URN =		{urn:nbn:de:0030-drops-277517},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.34},
  annote =	{Keywords: Pseudorandomness, lossless expanders, multiplicity codes, condensers}
}
Document
DOI: 10.4230/LIPIcs.CCC.2026.5
Condensing and Extracting Against Online Adversaries

Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract
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].
Cite as

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, and Rocco A. Servedio. Condensing and Extracting Against Online Adversaries. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 5:1-5:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2026.5,
  author =	{Chattopadhyay, Eshan and Gurumukhani, Mohit and Ringach, Noam and Servedio, Rocco A.},
  title =	{{Condensing and Extracting Against Online Adversaries}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{5:1--5:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.5},
  URN =		{urn:nbn:de:0030-drops-270477},
  doi =		{10.4230/LIPIcs.CCC.2026.5},
  annote =	{Keywords: collective coin flipping, leader election, Boolean function analysis, fault tolerant distributed computing, full information model, resilient function, pseudorandomness, condensers, adversarial sources, non-oblivious symbol fixing sources, Chor-Goldreich sources}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact