Two-Sided Lossless Expanders in the Unbalanced Setting

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

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2024-10
Main Authors: Chattopadhyay, Eshan, Gurumukhani, Mohit, Ringach, Noam, Zhao, Yunya
Format: Article
Language:English
Subjects:
Apexes
Expanders
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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\).
ISSN:2331-8422