Algorithmic Convexity in the Discrete World and the Resolution of a 30-Years-Old Conjecture
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.