[Colloquium] REMINDER: 5/19 Talks at TTIC: Shayan Oveis Charan, University of Washington

[Mary Marre]

When:     Thursday, May 19th at 3:00 pm

Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

Speaker:  Shayan Oveis Charan, University of Washington


Title: Applications of strongly Rayleigh distributions in Algorithm Design

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: Madhur Tulsiani, madhurt at ttic.edu





Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20160519/57fa5868/attachment.htm