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-years-old conjecture of Mihail and Vazirani that matroid polytopes have edge expansion at least 1.

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.