Two-Sided Lossless Expanders in the Unbalanced Setting
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909484723470336 |
|---|---|
| author | Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam Zhao, Yunya |
| author_facet | Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam Zhao, Yunya |
| contents | 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.
Using our unbalanced bipartite expander, we easily obtain lossless (non-bipartite) expander graphs on $N$ vertices with polynomial degree $\ll N$ and expanding sets of size $N^{0.49}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04549 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Two-Sided Lossless Expanders in the Unbalanced Setting Chattopadhyay, Eshan Gurumukhani, Mohit Ringach, Noam Zhao, Yunya Computational Complexity G.2.1; G.2.2 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. Using our unbalanced bipartite expander, we easily obtain lossless (non-bipartite) expander graphs on $N$ vertices with polynomial degree $\ll N$ and expanding sets of size $N^{0.49}$. |
| title | Two-Sided Lossless Expanders in the Unbalanced Setting |
| topic | Computational Complexity G.2.1; G.2.2 |
| url | https://arxiv.org/abs/2409.04549 |