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 see applications to sampling diverse sets based on volume.
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.
Nima Anari is a Microsoft research fellow at the Simons Institute for the Theory of Computing, and a research engineer at Stanford University, department of Computer Science. Prior to that, he obtained his Ph.D. in Computer Science from UC Berkeley, advised by Satish Rao, and continued as a postdoctoral scholar at Stanford University, department of MS&E.
He is interested in the design and analysis of algorithms, with a particular focus on the interplay between combinatorics, probability, and the geometry of polynomials.