ECCC-Report TR24-133https://eccc.weizmann.ac.il/report/2024/133Comments and Revisions published for TR24-133en-usTue, 01 Oct 2024 22:05:08 +0300
Revision 1
| Two-Sided Lossless Expanders in the Unbalanced Setting |
Eshan Chattopadhyay,
Mohit Gurumukhani,
Noam Ringach,
Yunya Zhao
https://eccc.weizmann.ac.il/report/2024/133#revision1We 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 $\ll N$.
Tue, 01 Oct 2024 22:05:08 +0300https://eccc.weizmann.ac.il/report/2024/133#revision1
Paper TR24-133
| Two-Sided Lossless Expanders in the Unbalanced Setting |
Eshan Chattopadhyay,
Mohit Gurumukhani,
Noam Ringach,
Yunya Zhao
https://eccc.weizmann.ac.il/report/2024/133 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 with high 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 $\ll N$.Sat, 07 Sep 2024 02:57:00 +0300https://eccc.weizmann.ac.il/report/2024/133