Lab Lunch: 12 February 2019 - Mary Cryan

Title: New results in approximate counting: Matroid bases and other problems

Abstract:

One of the long-open problems in approximate counting is the question of whether the "basis-exchange" for a general matroid is rapidly mixing. This question was recently resolved by Anari, Liu, Oveis Gharan and Vinzant, giving an FPRAS for counting bases of a general matroid. New results for other problems have followed. I will give a overview of these new results, my aim will be to make it as accessible as possible.