License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.12
URN: urn:nbn:de:0030-drops-116974
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11697/
Liu, Siqi ;
Mohanty, Sidhanth ;
Yang, Elizabeth
High-Dimensional Expanders from Expanders
Abstract
We present an elementary way to transform an expander graph into a simplicial complex where all high order random walks have a constant spectral gap, i.e., they converge rapidly to the stationary distribution. As an upshot, we obtain new constructions, as well as a natural probabilistic model to sample constant degree high-dimensional expanders.
In particular, we show that given an expander graph G, adding self loops to G and taking the tensor product of the modified graph with a high-dimensional expander produces a new high-dimensional expander. Our proof of rapid mixing of high order random walks is based on the decomposable Markov chains framework introduced by [Jerrum et al., 2004].
BibTeX - Entry
@InProceedings{liu_et_al:LIPIcs:2020:11697,
author = {Siqi Liu and Sidhanth Mohanty and Elizabeth Yang},
title = {{High-Dimensional Expanders from Expanders}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {12:1--12:32},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11697},
URN = {urn:nbn:de:0030-drops-116974},
doi = {10.4230/LIPIcs.ITCS.2020.12},
annote = {Keywords: High-Dimensional Expanders, Markov Chains}
}
|
Keywords: |
|
High-Dimensional Expanders, Markov Chains |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
