{"560051":{"#nid":"560051","#data":{"type":"event","title":"ARC Colloquium: David Karger (MIT)","body":[{"value":"\u003Cp style=\u0022color:maroon;\u0022\u003EVideo of this talk is available at: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/55915\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/55915\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:\/\/people.csail.mit.edu\/karger\/\u0022\u003E\u003Cstrong\u003EDavid Karger - MIT\u003C\/strong\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, September 26, 2016\u003Cbr \/\u003E\r\nKlaus 1116 East - 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u003Cbr \/\u003E\r\nA Fast and Simple Unbiased Estimator for Network (Un)reliability\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003Cbr \/\u003E\r\nThe following procedure yields an unbiased estimator for the disconnection probability of an n-vertex graph with minimum cut c if every edge fails independently with probability p: (i) contract every edge independently with probability 1-n^{-2\/c}, then (ii) recursively compute the disconnection probability of the resulting tiny graph if each edge fails with probability n^{2\/c}p.\u0026nbsp; We give a short, simple, self-contained proof that this estimator can be computed in linear time and has relative variance O(n^2).\u0026nbsp; Combining these two facts with a relatively standard sparsification argument yields an O(n^3\\log n)-time algorithm for estimating the (un)reliability of a network.\u0026nbsp; We also show how the technique can be used to create unbiased samples of disconnected networks.\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESpeaker\u0026#39;s webpage: \u003Ca href=\u0022http:\/\/people.csail.mit.edu\/karger\/\u0022\u003Ehttp:\/\/people.csail.mit.edu\/karger\/\u003C\/a\u003E\u003Cbr \/\u003E\r\nFall 2016 ARC Seminar Schedule: \u0026nbsp;\u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/114\u0022 target=\u0022_blank\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/114\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"A Fast and Simple Unbiased Estimator for Network (Un)reliability (Klaus 1116 E at 11am)"}],"uid":"27466","created_gmt":"2016-08-08 10:29:12","changed_gmt":"2017-04-13 21:15:12","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-09-26T12:00:00-04:00","event_time_end":"2016-09-26T13:00:00-04:00","event_time_end_last":"2016-09-26T13:00:00-04:00","gmt_time_start":"2016-09-26 16:00:00","gmt_time_end":"2016-09-26 17:00:00","gmt_time_end_last":"2016-09-26 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"115001","name":"Computational Complexity"},{"id":"114991","name":"Computational Learning Theory"},{"id":"109","name":"Georgia Tech"}],"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":""}}}