*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Vedat Levi Alev (Waterloo)
Monday, February 10, 2020
Klaus 1116 East - 11:00 am
Title: Improved Analysis of Higher Order Random Walks and Applications
Abstract: 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. We show some applications of this result in analyzing mixing times of Markov chains including sampling independent sets of a graph.
(https://arxiv.org/abs/2001.02827)
Joint work with: Lap Chi Lau
----------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu
