View abstract

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.

View abstract PDF