Spring 2019

Improved Analysis of Higher Order Random Walks

Tuesday, September 8th, 2020 11:30 am12:00 pm

Add to Calendar


Vedat Alev Levi (University of Waterloo)

Local spectral expansion is a very useful method for arguing about the spectral properties of several random walk matrices over simplicial complexes. The motivation of this work is to extend this method to analyze the mixing times of Markov chains for combinatorial problems. Our main result is a sharp upper bound on the second eigenvalue of the down-up walk on a pure simplicial complex, in terms of the second eigenvalues of its links. Our results have been applied to sampling independent sets from the hardcore distribution (ALO '20), sampling from the Gibbs distribution of 2-spin systems in the correlation decay regime (CLV '20), and sampling uniformly random colourings of a graph in the correlation decay regime (CGSV '20, FGYZ '20)

Joint work with: Lap Chi Lau