Algorithmic Convexity in the Discrete World

Nima Anari
Stanford University
Talk Series: 
04.15.2019 11:00 to 12:00
IRB 4105

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.