[Colloquium] Theory Seminars at Computer Science
Donna Brooms
donna at cs.uchicago.edu
Thu May 19 09:55:00 CDT 2016
*REMINDER*
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/20160519/cc3415d1/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/20160519/cc3415d1/attachment-0001.bin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160519/cc3415d1/attachment-0003.htm
More information about the Colloquium
mailing list