2026-07-23T13:08:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11697 2024-03-06T10:48:29Z ddc:004 open_access

High-Dimensional Expanders from Expanders Liu, Siqi Mohanty, Sidhanth Yang, Elizabeth High-Dimensional Expanders Markov Chains 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]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Siqi Liu and Sidhanth Mohanty and Elizabeth Yang 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.12 urn:nbn:de:0030-drops-116974 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.12 eng https://creativecommons.org/licenses/by/3.0/legalcode