License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.8
URN: urn:nbn:de:0030-drops-182780
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18278/
Go to the corresponding LIPIcs Volume Portal

Cohen, Gil ; Cohen, Itay

Spectral Expanding Expanders

pdf-format:
LIPIcs-CCC-2023-8.pdf (0.7 MB)

Abstract

Dinitz, Schapira, and Valadarsky [Dinitz et al., 2017] introduced the intriguing notion of expanding expanders - a family of expander graphs with the property that every two consecutive graphs in the family differ only on a small number of edges. Such a family allows one to add and remove vertices with only few edge updates, making them useful in dynamic settings such as for datacenter network topologies and for the design of distributed algorithms for self-healing expanders. [Dinitz et al., 2017] constructed explicit expanding-expanders based on the Bilu-Linial construction of spectral expanders [Bilu and Linial, 2006]. The construction of expanding expanders, however, ends up being of edge expanders, thus, an open problem raised by [Dinitz et al., 2017] is to construct spectral expanding expanders (SEE).
In this work, we resolve this question by constructing SEE with spectral expansion which, like [Bilu and Linial, 2006], is optimal up to a poly-logarithmic factor, and the number of edge updates is optimal up to a constant. We further give a simple proof for the existence of SEE that are close to Ramanujan up to a small additive term. As in [Dinitz et al., 2017], our construction is based on interpolating between a graph and its lift. However, to establish spectral expansion, we carefully weigh the interpolated graphs, dubbed partial lifts, in a way that enables us to conduct a delicate analysis of their spectrum. In particular, at a crucial point in the analysis, we consider the eigenvectors structure of the partial lifts.

BibTeX - Entry

@InProceedings{cohen_et_al:LIPIcs.CCC.2023.8,
  author =	{Cohen, Gil and Cohen, Itay},
  title =	{{Spectral Expanding Expanders}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18278},
  URN =		{urn:nbn:de:0030-drops-182780},
  doi =		{10.4230/LIPIcs.CCC.2023.8},
  annote =	{Keywords: Expanders, Normalized Random Walk, Spectral Analysis}
}

Keywords: Expanders, Normalized Random Walk, Spectral Analysis
Collection: 38th Computational Complexity Conference (CCC 2023)
Issue Date: 2023
Date of publication: 10.07.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI