“High-Dimensional Markov Chains and Applications”
Abstract: A Markov chain is a random process in which the next state is chosen according to some probability distribution that depends only on the current state. In a high-dimensional setting, Markov chains are essential tools for understanding the geometry of the space and form the backbone of many efficient randomized algorithms for tasks like optimization, integration, linear programming, approximate counting, etc. In this talk, I will provide an overview of my research on “High-Dimensional Markov Chains,” with a focus on the geometric aspects of the chains. I will describe two results that illustrate the importance of Markov chains for designing efficient algorithms. First, I will discuss my work on a barrier-based random walk for bounding the discrepancy of set systems. I will then present a general framework for bounding discrepancy in various settings. Second, I will describe two Markov chains, the Weighted Dikin Walk and Coordinate Hit-and-Run for sampling convex bodies, and discuss new techniques for bounding their convergence rates.
This seminar was held virtually over zoom and no recording is available.
