Algorithms & Randomness Center (ARC)

Shayan Oveis Gharan – University of Washington

Monday, September 12, 2016

Klaus 1116 East - 11am

Title:  Strongly Rayleigh distributions and their Applications 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, and closure under conditioning and truncation.
In this talk I will go over basic properties of these distributions, and then I will describe several algorithmic applications.
Based on joint works with Nima Anari, Alireza Rezaei, Mohit Singh, Amin Saberi.

Bio:

Shayan Oveis Gharan is an assistant professor in the computer science and engineering department at University of Washington.  He received his PhD from the MS&E department at Stanford University in 2013 advised by Amin Saberi and Luca Trevisan.  Before joining UW he spent one and a half years as a postdoctoral Miller Fellow at UC Berkeley where his host was Umesh Vazirani. He did his undergraduate studies at the Computer Engineering department at Sharif University.
Shayan's research includes Algorithm design, Graph Theory and Applied Probability.  He received ACM doctoral dissertation award honorable mention for his PhD thesis "New Rounding Techniques for the Design and Analysis of Approximation Algorithms" in 2013. He and his coauthors received best paper awards at SODA 2010 and FOCS 2011 for their works on the Traveling Salesman Problem.

URL: http://homes.cs.washington.edu/~shayan/