Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

We design the first fully polynomial-time randomized approximation scheme (FPRAS) for approximately counting and uniformly sampling common bases of two matroids given by their independence oracles. Moreover, our algorithms generalize far beyond this to Hadamard products of two probability measures on the Boolean cube satisfying a simple nonnegative curvature condition. A small sample of consequences include the first efficient algorithms for computing the partition function of the EPR model in quantum many-body physics, the mixed volume of arbitrary convex bodies in any dimension, the number of Euler tours in a graph, the number of contingency tables (with polynomially bounded entries), etc. Our algorithms are based on a novel combination of Markov chain Monte Carlo and convex programming, and the analysis relies on a uniform Poincare Inequality that is proved via an integrated Bochner-type method. Joint work with Xiaoyu Chen.