# Explicit Lossless Vertex Expanders

arXiv: https://arxiv.org/abs/2504.15087 · HTML: https://mlsanity.com/paper/2504.15087/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Apr 2025.

## Built on by (most cited first, 1 of 1)

- [Spiky Rank and Its Applications to Rigidity and Circuits](https://mlsanity.com/paper/2602.23503/) (2026)

## Abstract (arXiv)

We give the first construction of explicit constant-degree lossless vertex expanders. Specifically, for any varepsilon > 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-varepsilon)d|S| neighbors (which implies (1-2varepsilon)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.