STOC2024
Explicit Two-Sided Unique-Neighbor Expanders
Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, Pedro Paredes
2 citations
Abstract
We study the problem of constructing explicit sparse graphs that exhibit strong vertex expansion. Our main result is the first two-sided construction of imbalanced unique-neighbor expanders, meaning bipartite graphs where small sets contained in both the left and right bipartitions exhibit unique-neighbor expansion, along with algebraic properties relevant to constructing quantum codes.