Session II.3 - Real-Number Complexity
Thursday, June 15, 17:30 ~ 18:00
Strongly Rayleigh distributions and Applications in Algorithm Design
Shayan Oveis Gharan
University of Washington, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
A multivariate polynomial $p(z_1,\dots,z_n)$ is stable if $p(z_1,\dots,z_n)\neq 0$ whenever $\Im(z_i) \gt 0$ for all $I$. Strongly Rayleigh distributions are probability distributions on Bernoulli random variables whose generating polynomial is stable. They can be seen as a natural generalization of product distributions. It is shown these distributions satisfy the strongest form of negative dependence properties one can consider.
In this talk I will go over basic properties of these distributions, and then I will describe some algorithmic applications.