Show simple item record

dc.contributor.authorAnari, Nima
dc.date.accessioned2018-05-17T19:24:03Z
dc.date.available2018-05-17T19:24:03Z
dc.date.issued2018-04-30
dc.identifier.urihttp://hdl.handle.net/1853/59687
dc.descriptionPresented on April 30, 2018 at 12:00 p.m. in the Klaus Advanced Computing Building, Room 1116E.en_US
dc.descriptionNima Anari is a researcher in the Computer Science Theory Group at Stanford University. He is broadly interested in the design and analysis of algorithms and more generally theoretical computer science.en_US
dc.descriptionRuntime: 58:32 minutesen_US
dc.description.abstractWe 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.en_US
dc.format.extent58:32 minutes
dc.language.isoen_USen_US
dc.relation.ispartofseriesARC Colloquiumen_US
dc.subjectEntropyen_US
dc.subjectMatroidsen_US
dc.titleEntropy, Log-Concavity, and a Deterministic Approximation Algorithm for Counting Bases of Matroidsen_US
dc.typeLectureen_US
dc.typeVideoen_US
dc.contributor.corporatenameGeorgia Institute of Technology. Algorithms, Randomness and Complexity Centeren_US
dc.contributor.corporatenameStanford University. Dept. of Computer Scienceen_US


Files in this item

This item appears in the following Collection(s)

  • ARC Talks and Events [68]
    Distinguished lectures, colloquia, seminars and speakers of interest to the ARC community

Show simple item record