Description

The short course will begin with the basics of expanders graphs, and Markov chain mixing times. We will then see one way to generalize the idea of expansion in graphs to simplicial complexes/hypergraphs introduced by Kaufman-Oppenheim. The goal is then to study a natural Markov chain on the maximal faces/hyperedges. We will introduce log-concavity and show that if the generating polynomial of the maximal faces is log-concave, then the Markov chain mixes rapidly. We will further show how to reduce proving log-concavity to proving log-concavity of quadratic polynomials obtained via differentiation. Finally, we will discuss applications of this machinery to sampling bases of a matroid, estimating the partition function of the Potts model in a new parameter region, and sampling from a "smoothed" DPP. Some open problems will be presented at the end.

Based on joint works with Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant

All scheduled dates:

Upcoming

No Upcoming activities yet

Past