2026-09-10T09:44:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27751 2026-09-09T12:19:36Z ddc:004 open_access

Two-Sided Lossless Expanders in the Unbalanced Setting Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam Zhao, Yunya Pseudorandomness lossless expanders multiplicity codes condensers 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eshan Chattopadhyay and Mohit Gurumukhani and Noam Ringach and Yunya Zhao 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.34 urn:nbn:de:0030-drops-277517 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.34 eng https://creativecommons.org/licenses/by/4.0/legalcode