Strongly log concave polynomials, high dimensional simplicial complexes, and an FPRAS for counting Bases of Matroids

Strongly log concave polynomials...Bases of Matroids - Shayan Oveis Gharan

Shayan Oveis Gharan
University of Washington
February 25, 2019

A matroid is an abstract combinatorial object which generalizes the notions of spanning trees,
and linearly independent sets of vectors. I will talk about an efficient algorithm based on the Markov Chain Monte Carlo technique
to approximately count the number of bases of any given matroid. 

The proof is based on a new connections between high dimensional simplicial complexes, and a new class
of multivariate polynomials called completely log-concave polynomials. In particular, we exploit a fundamental fact from our
previous work that the bases generating polynomial of any given matroid is a log-concave function over the positive orthant. 

Based on joint works with Nima Anari, Kuikui Liu, and Cynthia Vinzant.