Special Colloquium
Nima Anari
Stanford
Algorithmic Convexity in the Discrete World
Abstract: A central algorithmic question is when can we efficiently sample from probability distributions?
In the continuous setting, convex sets and more generally log-concave distributions are the
main objects from which we can efficiently produce samples. In this talk, I will define a
parallel theory of convexity for discrete distributions and show how to use it to obtain
efficient sampling, counting, and optimization algorithms.
The main tool behind this theory consists of polynomials that encode discrete objects and
distributions, and the study of their analytical properties. This allows us to associate a
``continuous geometry’’ to discrete objects, and relate notions of convexity in the discrete
and continuous worlds.
We resolve several long-standing problems. This include sampling uniformly from bases
or independent sets of matroids, determinantal point processes and fractional powers of
them, and the random cluster (or Potts) model in the ``negative dependence regime'’ of q<1.
We also resolve a structural conjecture of Mason on the number of independent sets in
matroids, and derive Van der Waerden-type inequalities for matroids.
Note the unusual time! A small Tea in SEO 636 will be at 3pm (right after the talk)
Tuesday February 26, 2019 at 2:00 PM in 636 SEO