Explicit Two-Sided Unique-Neighbor Expanders

Jun Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, Pedro Paredes

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus 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. Our constructions are obtained from instantiations of the tripartite line product of a large tripartite spectral expander and a sufficiently good constant-sized unique-neighbor expander, a new graph product we defined that generalizes the line product and the routed product of previous well-known works. To analyze the vertex expansion of graphs arising from the tripartite line product, we develop a sharp characterization of subgraphs that can arise in bipartite spectral expanders, generalizing previously known results, which may be of independent interest. By picking appropriate graphs to apply our product to, we give a strongly explicit construction of an infinite family of (d1,d2)-biregular graphs (Gn)n≥ 1 (for large enough d1 and d2) where all sets S with fewer than a small constant fraction of vertices have ω(d1· |S|) unique-neighbors (assuming d1 ≤ d2). Additionally, we can also guarantee that subsets of vertices of size up to exp(ω(√log|V(Gn)|)) expand losslessly.

Original languageEnglish (US)
Title of host publicationSTOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing
EditorsBojan Mohar, Igor Shinkar, Ryan O�Donnell
PublisherAssociation for Computing Machinery
Pages788-799
Number of pages12
ISBN (Electronic)9798400703836
DOIs
StatePublished - Jun 10 2024
Event56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada
Duration: Jun 24 2024Jun 28 2024

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference56th Annual ACM Symposium on Theory of Computing, STOC 2024
Country/TerritoryCanada
CityVancouver
Period6/24/246/28/24

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Algebraic expanders
  • Lossless expanders
  • Unique-neighbor expanders

Fingerprint

Dive into the research topics of 'Explicit Two-Sided Unique-Neighbor Expanders'. Together they form a unique fingerprint.

Cite this