Short Course

Speaker(s): 
Shayan Oveis Gharan
Title: 
Log Concave Polynomials, Entropy and Deterministic Approximation Algorithm for Counting Bases of a Matroid
Abstract: 

we give a deteministic 2O(rank)- approximation algorithm to count the number of bases of a given matroid and the number of common bases of any two matroids. 
there are two main ingerediants in our results: for the first ingerediant, we build upon recent results of Huh-Wang and Adiprasito - Huh-Katz on combinatorial hodge theory to derive a connection between matroids and log-concave polynomials. 
Formally, we prove that the multvariate generating polynomials of the bases of any matroid is log-concave as a function over the positive orthant. for the second ingerediant, we use a general framework for appriximate counting in discrete problems, based on convex optimization and sub-additivility of the entropy. 
for matroids, we prove that an approximate super additivity of the entripy holds, yielding an approxiamation algorithm, by relying on log-concavity of the corresponding polynomials. 
this is a joint work with Nima Anari and Cynthia Vinzant.