[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

THEORY SEMINAR

Tuesday, May 19, 2016
3:00 pm
TTIC-526

Shayan Oveis Gharan
Title:  “Applications of strongly Rayleigh distributions in Algorithm”    
 
Abstract: 
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, concentration of measure, and closure under conditioning and truncation.

In this talk I will describe how to use the properties of strongly Rayleigh distributions to design and analyze algorithms. In particular, we will see applications to symmetric and asymmetric TSP and the volume sampling problem.

Based on joint works with Nima Anari, Alireza Rezaei, Mohit Singh, Amin Saberi.

Host: Prof. Madhur Tulsiani

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160517/7eaa7718/attachment-0002.htm 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Shayan Oveis Gharan.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 260561 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160517/7eaa7718/attachment-0001.bin 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160517/7eaa7718/attachment-0003.htm