UCSB CS Theory Colloquium Series

Fall 2021

Friday, October 29, 2pm, Phelps 2510
                Speaker: Thuy-Duong Vuong (Stanford)
                Title: Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More
Abstract:
We show fully polynomial time randomized approximation schemes for counting matchings of a given size, or more generally sampling/counting monomer-dimer systems in planar, not-necessarily-bipartite, graphs. While perfect matchings on planar graphs can be counted exactly in polynomial time, counting non-perfect matchings was shown by [Jer87] to be #P-hard, who also raised the question of whether efficient approximate counting is possible. We answer this affirmatively by showing that the multi-site Glauber dynamics on the set of monomers in a monomer-dimer system always mixes rapidly, and that these dynamics can be implemented efficiently on families of graphs where counting perfect matchings is tractable.

In order to analyze mixing properties of the multi-site Glauber dynamics, we establish two new notions for generating polynomials of discrete set-valued distributions: sector-stability and fractional log-concavity. These notions generalize well-studied properties like real-stability and log-concavity, but unlike them robustly degrade under useful transformations applied to the distribution. We relate these notions to pairwise correlations in the underlying distribution and the notion of spectral independence introduced by [ALO20], providing a new tool for establishing spectral independence based on geometry of polynomials. As a byproduct of our techniques, we show that polynomials avoiding certain regions of the complex plane must satisfy a form of convexity, extending a classical result established between hyperbolic and log-concave polynomials by [Gar59] to new classes of polynomials.
As further applications of our results, we show how to sample efficiently from partition-constrained strongly Rayleigh distributions, and certain asymmetric determinantal point processes using natural Markov chains.

--based on joint work with Yeganeh Alimohammadi, Nima Anari and Kiran Shiragur