{"601407":{"#nid":"601407","#data":{"type":"event","title":"ARC Colloquium: Di Wang (Berkeley\/GaTech)","body":[{"value":"\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\u003Cstrong\u003EDi Wang\u0026nbsp;(UC Berkeley\/Georgia Tech)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 5, 2018\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East\u0026nbsp;- 11:00 am\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp; \u0026nbsp;Capacity Releasing Diffusion for Speed and Locality\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp; \u003C\/strong\u003E \u0026nbsp; Diffusion and related random walk procedures on graphs are of central importance in many areas of machine learning, data analysis, and algorithm design. Because they spread mass agnostically at each step in an iterative manner, they can sometimes spread mass \u0026ldquo;too aggressively,\u0026rdquo; thereby failing to find the \u0026ldquo;right\u0026rdquo; clusters. We introduce a novel Capacity Releasing Diffusion (CRD) Process, which is both faster and stays more local than the classical probability mass diffusion.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThe CRD Process follows a carefully-constructed push-relabel rule, using techniques that are well-known from flow-based graph algorithms. While \ufb02ow and probability mass diffusion (or more generally, spectral methods) have a long history of competing to provide good graph decomposition, local methods are predominantly based on diffusion. Our CRD Process is the \ufb01rst primarily \ufb02ow-based local method for locating low conductance cuts, and it has exhibited improved theoretical and empirical behavior over classical di\ufb00usion methods, e.g. PageRank.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003EVideos of recent talks are available at: \u003C\/em\u003E\u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003E\u003Cem\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003E\u003Cem\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/em\u003E\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":"Capacity Releasing Diffusion for Speed and Locality - Klaus 1116E at 11am"}],"uid":"32895","created_gmt":"2018-01-26 16:49:55","changed_gmt":"2018-01-26 19:37:42","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-02-05T11:00:00-05:00","event_time_end":"2018-02-05T12:00:00-05:00","event_time_end_last":"2018-02-05T12:00:00-05:00","gmt_time_start":"2018-02-05 16:00:00","gmt_time_end":"2018-02-05 17:00:00","gmt_time_end_last":"2018-02-05 17:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"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"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}