Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-133 | 1st October 2024 22:05

Two-Sided Lossless Expanders in the Unbalanced Setting

RSS-Feed




Revision #1
Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Yunya Zhao
Accepted on: 1st October 2024 22:05
Downloads: 60
Keywords: 


Abstract:

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 $\ll N$.



Changes to previous version:

Improvements in our main results from the earlier version


Paper:

TR24-133 | 7th September 2024 02:10

Two-Sided Lossless Expanders in the Unbalanced Setting


Abstract:

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$.



ISSN 1433-8092 | Imprint