*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Nima Anari
Monday, April 30, 2018
Klaus 1116 East – Noon
Title: Entropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroids
Abstract: We give a deterministic 2^O(rank) approximation algorithm to count the number of bases of a given matroid and the number of common bases of any two matroids. Based on a lower bound of Azar et al., this is almost the best possible result assuming oracle access to independent sets of matroids.
There are two main ingredients in our result: For the first ingredient, we build upon recent results of Huh et al. and Adiprasito et al. on combinatorial hodge theory to derive a connection between matroids and log-concave polynomials. We expect that several new applications in approximation algorithms will be derived from this connection in future. Formally, we prove that the multivariate generating polynomial of the bases of any matroid is log-concave as a function over the positive orthant. For the second ingredient, we use a general framework for approximate counting in discrete problems, based on convex optimization and sub-additivity of the entropy. For matroids, we prove that an approximate super-additivity of the entropy holds, yielding an approximation algorithm, by relying on log-concavity of the corresponding polynomials.
Joint work with Shayan Oveis Gharan and Cynthia Vinzant.
----------------------------------
Videos of recent talks are available at https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
