{"550161":{"#nid":"550161","#data":{"type":"event","title":"ARC Colloquium:  Shayan Oveis Gharan (Washington)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/55876\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/55876\u003C\/a\u003E\u003C\/p\u003E\r\nFull collection of talk videos are available at:  \r\n\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/a\u003E\r\n\r\n\u003Cbr\u003E\r\n\u003Cbr\u003E\r\n\r\n\r\n\u003Cp  align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp  align=\u0022center\u0022\u003E\u003Ca href=\u0022http:\/\/homes.cs.washington.edu\/~shayan\/\u0022\u003E\u003Cstrong\u003EShayan Oveis Gharan \u0026ndash; \u003C\/strong\u003E\u003Cstrong\u003EUniversity of Washington\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp  align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 12, 2016\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp  align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 11am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle: \u0026nbsp;\u003C\/strong\u003E\u003Cem\u003EStrongly Rayleigh distributions and their Applications in Algorithm Design\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EA multivariate polynomial p(z1,...,zn) is stable if p(z1,...,zn) \u0026lt;\u0026gt; 0 whenever Im(zi)\u0026gt;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.\u0026nbsp;Borcea, Branden and Liggett used\u0026nbsp;the geometry of stable polynomials to prove numerous properties of strongly Rayleigh distributions,\u0026nbsp;including negative association, and closure under conditioning and truncation.\u003Cbr \/\u003E\r\nIn this talk I will go over basic properties of these distributions, and then I will describe several algorithmic applications.\u003Cbr \/\u003E\r\nBased on joint works with Nima Anari, Alireza Rezaei,\u0026nbsp;Mohit Singh, Amin Saberi.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EBio:\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EShayan Oveis Gharan is an assistant professor in the \u003Ca href=\u0022https:\/\/www.cs.washington.edu\u0022\u003Ecomputer science and engineering\u003C\/a\u003E department at \u003Ca href=\u0022http:\/\/uw.edu\u0022\u003EUniversity of Washington\u003C\/a\u003E.\u0026nbsp; He received his PhD from the \u003Ca href=\u0022http:\/\/msande.stanford.edu\u0022\u003EMS\u0026amp;E department\u003C\/a\u003E at \u003Ca href=\u0022http:\/\/stanford.edu\u0022\u003EStanford University\u003C\/a\u003E in 2013 advised by \u003Ca href=\u0022http:\/\/stanford.edu\/%7Esaberi%22\u0022\u003EAmin Saberi\u003C\/a\u003E and \u003Ca href=\u0022http:\/\/www.eecs.berkeley.edu\/%7Eluca\/\u0022\u003ELuca Trevisan\u003C\/a\u003E.\u0026nbsp; Before joining \u003Ca href=\u0022http:\/\/www.washington.edu\/\u0022\u003EUW\u003C\/a\u003E he spent one and a half years as a postdoctoral \u003Ca href=\u0022http:\/\/millerinstitute.berkeley.edu\u0022\u003EMiller Fellow\u003C\/a\u003E at \u003Ca href=\u0022http:\/\/www.berkeley.edu\/\u0022\u003EUC Berkeley\u003C\/a\u003E where his host was \u003Ca href=\u0022http:\/\/www.cs.berkeley.edu\/%7Evazirani\/\u0022\u003EUmesh Vazirani\u003C\/a\u003E. He did his undergraduate studies at the \u003Ca href=\u0022http:\/\/ce.sharif.edu\u0022\u003EComputer Engineering department\u003C\/a\u003E at \u003Ca href=\u0022http:\/\/sharif.edu\u0022\u003ESharif University\u003C\/a\u003E.\u003Cbr \/\u003E\r\nShayan\u0026#39;s research includes Algorithm design, Graph Theory and Applied Probability.\u0026nbsp; He received ACM doctoral dissertation award honorable mention for his PhD thesis \u0026quot;New Rounding Techniques for the Design and Analysis of Approximation Algorithms\u0026quot; in 2013. He and his coauthors received best paper awards at SODA 2010 and FOCS 2011 for their works on the Traveling Salesman Problem.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EURL: \u003Ca href=\u0022http:\/\/homes.cs.washington.edu\/~shayan\/\u0022\u003Ehttp:\/\/homes.cs.washington.edu\/~shayan\/\u003C\/a\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Strongly Rayleigh distributions and their Applications in Algorithm Design (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-07-01 15:50:54","changed_gmt":"2017-04-13 21:15:26","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-09-12T12:00:00-04:00","event_time_end":"2016-09-12T13:00:00-04:00","event_time_end_last":"2016-09-12T13:00:00-04:00","gmt_time_start":"2016-09-12 16:00:00","gmt_time_end":"2016-09-12 17:00:00","gmt_time_end_last":"2016-09-12 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"related_links":[{"url":"http:\/\/homes.cs.washington.edu\/~shayan\/","title":"Shayan Oveis Gharan"}],"groups":[{"id":"70263","name":"ARC"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[{"id":"92341","name":"Algorithms and Randomness Center"},{"id":"4265","name":"ARC"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"78751","name":"Undergraduate students"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003C\/p\u003E\r\n\r\n\u003Cp\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\r\n","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}