*********************************
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)
Jonathan Hermon (Cambridge)
Monday, November 27, 2017
Klaus 1116 East - 11:00 am
Title: A characterization of $L_p$ mixing, cutoff and hypercontractivity via maximal inequalities and hitting times.
Abstract: (joint work with Yuval Peres): There are several works characterizing the total-variation mixing time of a reversible Markov chain in term of natural probabilistic concepts such as stopping times and hitting times. In contrast, there is no known analog for the uniform ($L_{\infty}$) mixing time (UMT), (there is neither a sharp bound nor one possessing a probabilistic interpretation). We show that the UMT can be characterized up to a constant factor using hitting times distributions. We also derive a new extremal characterization of the Log-Sobolev constant, $c_{LS}$, as a weighted version of the spectral gap. This characterization yields a probabilistic interpretation of $c_{LS}$ in terms of a hitting time version of hypercontractivity. As applications, we (1) resolve a conjecture of Kozma by showing that the UMT is not robust under rough isometries (even in the bounded degree, unweighted setup), (2) show that for weighted nearest neighbor random walks on trees, the UMT is robust under bounded perturbations of the edge weights, and (3) Establish a general robustness result under addition of weighted self-loops.
--------------------------------------
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@cc.gatech.edu
