Computer Science/Discrete Mathematics Seminar I

We introduce two new notions for polynomials associated with discrete set-valued probability distributions. These notions generalize well-studied properties like real-stability and log-concavity, but unlike them robustly degrade under a number of useful transformations applied to the polynomial/distribution. We show that these notions imply polynomial time approximate sampling and counting algorithms through rapid mixing of multi-site Glauber dynamics. We establish the new notions for polynomials/distributions related to matchings, Pfaffian point processes, and partition-constrained strongly Rayleigh measures with O(1) partitions. As the main application we show how to approximately count matchings of a desired size k, or sample from the monomer-dimer distribution, in arbitrary planar graphs (not necessarily bipartite) in polynomial time; this answers a question raised by Jerrum in 1987 who proved intractability of exact counting in the planar case. Joint work with Yeganeh Alimohammadi, Kirankumar Shiragur, and Thuy-Duong Vuong.