Title: Explicit Lossless Vertex Expanders
| Speaker: |
Sidhanth Mohanty |
| Affiliation: |
Massachusetts Institute of Technology |
| Location: | Please contact Sabrina Lato for Zoom link. |
Abstract: We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any ε>0 and sufficiently large d, we give an explicit construction of an infinite family of d-regular graphs where every small set S of vertices has (1−ε)d|S| neighbors (which implies (1−2ε)d|S| unique-neighbors). Our results also extend naturally to construct biregular bipartite graphs of any constant imbalance, where small sets on each side have strong expansion guarantees. The graphs we construct admit a free group action, and hence realize new families of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding algorithm.
Our construction is based on taking an appropriate product of a constant-sized lossless expander with a base graph constructed from Ramanujan Cayley cubical complexes.
Based on joint work with Jun-Ting Hsieh, Alexander Lubotzky, Assaf Reiner, and Rachel Yun Zhang (https://arxiv.org/abs/2504.15087)