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: https://drops.dagstuhl.de/opus/volltexte/2020/11697/
Liu, Siqi ; Mohanty, Sidhanth ; Yang, Elizabeth
High-Dimensional Expanders from Expanders
| pdf-format: |
|
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 | |
| Seminar: | 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 06.01.2020 |
