Rapidly mixing random walks on matroids and related objectsidly mixing random walks on matroids and related objects

Seminar | May 1 | 3-4 p.m. | 1011 Evans Hall

 Nima Anari, Stanford University

 Department of Statistics

A central question in randomized algorithm design is what kind of distributions can we sample from efficiently? On the continuous side, uniform distributions over convex sets and more generally log-concave distributions constitute the main tractable class. We will build a parallel theory on the discrete side, that yields tractability for a large class of discrete distributions. We will use this theory to resolve a 30-year-old conjecture of Mihail and Vazirani that matroid polytopes have edge expansion at least 1. We will also obtain simple nearly-linear time algorithms for sampling from spanning trees of a graph, and easy-to-implement algorithms for volume-based sampling.
The hammer enabling these algorithmic advances is the introduction and the study of a class of polynomials, that we call completely log-concave. We can use very simple and easy-to-implement random walks to perform the task of sampling, and we will use completely log-concave polynomials to analyze the random walk. Based on joint work with Kuikui Liu, Shayan Oveis Gharan, Cynthia Vinzant.