Computer Science/Discrete Mathematics Seminar I | |

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

Speaker: | Shayan Oveis Gharan |

Affiliation: | University of Washington |

Date: | Monday, February 25 |

Time/Room: | 11:00am - 12:00pm/Simonyi Hall 101 |

Video Link: | https://video.ias.edu/csdm/2019/0225-ShayanOveisGharan |

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.