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.