Strongly Rayleigh distributions and their Applications in Algorithm Design
Gharan, Shayan Oveis
MetadataShow full item record
A multivariate polynomial p(z1,...,zn) is stable if p(z1,...,zn) <> 0 whenever Im(zi)>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 product 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 these distributions, and then I will describe several algorithmic applications. Based on joint works with Nima Anari, Alireza Rezaei, Mohit Singh, Amin Saberi.