Improved Analysis of Higher Order Random Walks
This event is free and open to the publicAdd to Google Calendar
Abstract: Local spectral expansion is a very useful method for arguing about the spectral properties of several random walk matrices over simplicial complexes. 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. We discuss some applications of this result in analyzing mixing times of Markov chains which include some recent breakthroughs in sampling problems.