The MCMC method and High Dimensional Expanders
The field of spectral graph theory classically studies the first few eigenvalues of matrices associated to a graph and relates them to combinatorial properties of the graph and the behavior of the simple random walk on the graph. In particular, it is known that if the second (largest) eigenvalue of the transition probability matrix of a graph is bounded away from one, i.e., the graph is an expander, then the simple random walk “mixes” in time logarithmic in the size of the graph.
Over the last decade, researchers managed to extend these machineries to high dimensional simplicial complexes and use them to analyze mixing time of Markov chains on exponentially largest state spaces. In this talk first I will give an overview of this connection and then I will explain a new machinery to prove that a high dimensional simplicial complex is an expander. For concrete applications, I will discuss how to use this technique to sample bases of a matroid or random edge colorings of a graph.
Shayan Oveis Gharan is an associate professor in the Paul Allen School of Computer Science and Engineering at University of Washington. He received his PhD from Stanford University in 2013 advised by Amin Saberi and Luca Trevisan. Before joining UW he spent one and a half years as a postdoctoral Miller Fellow at UC Berkeley.
Shayan’s research exploits tools in Mathematics such as probability theory, theory of real stable and log-concave polynomials, and spectral graph theory to design and analyze algorithms for discrete objects.