## 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. document.getElementById('cloakef397ab87b465ff754c58d51fd8d23eb').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addyef397ab87b465ff754c58d51fd8d23eb = 'sh&#97;y&#97;n' + '&#64;'; addyef397ab87b465ff754c58d51fd8d23eb = addyef397ab87b465ff754c58d51fd8d23eb + 'cs' + '&#46;' + 'w&#97;sh&#105;ngt&#111;n' + '&#46;' + '&#101;d&#117;'; var addy_textef397ab87b465ff754c58d51fd8d23eb = 'sh&#97;y&#97;n' + '&#64;' + 'cs' + '&#46;' + 'w&#97;sh&#105;ngt&#111;n' + '&#46;' + '&#101;d&#117;';document.getElementById('cloakef397ab87b465ff754c58d51fd8d23eb').innerHTML += '<a ' + path + '\'' + prefix + ':' + addyef397ab87b465ff754c58d51fd8d23eb + '\'>'+addy_textef397ab87b465ff754c58d51fd8d23eb+'<\/a>';

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.