Algorithmic Convexity in the Discrete World and the Resolution of a 30-Years-Old Conjecture

Date: March 14, 2019
Time: 2:00 pm
Room: DBH 4011
Speaker: Nima Anari 
(Stanford University)

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.


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.

Close Menu
Skip to content