Abstract
The Markov Chain Monte Carlo paradigm is one of the most widely used methods for sampling from challenging distributions, both practically and theoretically. Tools for determining the efficiency of a Markov chain sampling algorithm have traditionally fallen into roughly two categories. On the one hand, we have purely "local" methods such as path coupling, which have elegant analyses and often give tight running times, but in some instances, are provably unable to certify rapid mixing even when other methods can. On the other hand, we have more "global" methods such as canonical paths/flows, which directly certify expansion of the state space, but typically have very involved analyses which are difficult to carry out in the absence of nice symmetry properties. High-dimensional expansion serves as a bridge between the local and the global, and connects many areas such as the geometry of polynomials, statistical physics, theoretical computer science, and combinatorics. We discuss a recent line of work that employs techniques from the area of high-dimensional expanders to analyzing Markov chains. Specific applications include sampling from bases of matroids and two-state spin systems.
Based on joint works with Nima Anari, Zongchen Chen, Shayan Oveis Gharan, Eric Vigoda, and Cynthia Vinzant.