Summer 2019

High-Dimensional Expanders from Expanders

Monday, Jul. 29, 2019 10:00 am11:00 am PDT

Add to Calendar


Siqi Liu


Room 116

We present an elementary way to transform an expander graphinto a simplicial complex where all high order random walks have 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 [JST+04]. In this talk we will present the construction, prove the local and global expansions and give the general proof idea of rapid mixing of high order random walks. [Joint work w/ Sidhanth Mohanty, Elizabeth Yang]