Frontiers in Mathematical Sciences

Real Stable Polynomials, Strongly Rayleigh Distributions and Algorithmic Applications

Shayan Oveis Gharan
University of Washington


A multivariate polynomial $p \left( z_1 , \ldots , z_n \right)$ is stable if $p \left( z_1 , \ldots , z_n \right) \neq 0$ whenever $\Im(z_i) > 0$ for all $i$. Strongly Rayleigh distributions are probability distributions on $0-1$ random variables whose generating polynomial is stable. They can be seen as a natural generalization of determinantal distributions. Borcea, Branden and Liggett used the geometry of stable polynomials to prove numerous properties of strongly Rayleigh distributions, including negative association, and closure under conditioning and truncation.
In this talk I will go over basic properties of stable polynomials and strongly Rayleigh distributions; then, I will describe algorithmic applications in counting, sampling and optimization.
Based on joint works with Nima Anari, Alireza Rezaei, Amin Saberi, Mohit Singh.