skip to main content
Caltech
Fires burning in Greater Los Angeles area have had significant impact on the Caltech's community and surrounding areas. For information and resources for members of the Caltech community, go to https://www.caltech.edu/fire.

TCS+ Talk

Wednesday, March 6, 2019
10:00am to 11:00am
Add to Cal
Annenberg 322
Strongly log concave polynomials, high dimensional simplicial complexes, and an FPRAS for counting Bases of Matroids
Shayan Oveis Gharan, University of Washington,

Abstract:

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.

For more information, please contact Bonnie Leung by email at bjleung@caltech.edu.