{"500221":{"#nid":"500221","#data":{"type":"event","title":"ARC Colloquium: Marco-Dick Yun Kuen Cheung - University of Vienna","body":[{"value":"\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EAlgorithms \u0026amp; Randomness Center (ARC) \u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMarco-Dick Yun Kuen Cheung \u0026nbsp;- University of Vienna\u003Cbr \/\u003E\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EMonday, February 29, 20116\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 West - 1:00 pm\u003C\/strong\u003E\u003C\/p\u003E\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003E(Refreshments will be served in Klaus 2222 at 2 pm)\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETitle: \u003Cbr \/\u003E \u003C\/strong\u003EGraph Minors for Preserving Terminal Distances Approximately\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003Cbr \/\u003E \u003C\/strong\u003EGiven a graph where vertices are partitioned into k terminals and non-terminals, the goal is to compress the graph (i.e., reduce the number of non-terminals) using minor operations while preserving terminal distances approximately. The distortion of a compressed graph is the maximum multiplicative blow-up of distances between all pairs of terminals. We study the trade-off between the number of non-terminals and the distortion.\u0026nbsp; This problem generalizes the Steiner Point Removal (SPR) problem, in which all non-terminals must be removed.\u003Cbr \/\u003E \u003Cbr \/\u003E We introduce a novel black-box reduction to convert any lower bound on distortion for the SPR problem into a super-linear lower bound on the number of non-terminals, with the same distortion, for our problem. This allows us to show that there exist graphs such that every minor with distortion less than 2 \/ 2.5\/ 3\u0026nbsp; must have \\Omega(k^2) \/ \\Omega(k^{5\/4}) \/ \\Omega(k^{6\/5}) non-terminals, plus more trade-offs in between. The black-box reduction has an interesting consequence: if the tight lower bound on distortion for the SPR problem is super-constant, then allowing any linear (in k) non-terminals will \u003Cem\u003Enot\u003C\/em\u003E help improving the lower bound to a constant.\u003Cbr \/\u003E \u003Cbr \/\u003E We also build on the existing results on spanners, distance oracles and connected 0-extensions to show a number of upper bounds for general graphs, planar graphs, graphs that exclude a fixed minor and bounded treewidth graphs. Among others, we show that any graph admits a minor with O(log k) distortion and O(k^2) non-terminals, and any planar graph admits a minor with $1+epsilon$ distortion and O(k^2 log^2 k \/ epsilon^2) non-terminals.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Klaus 1116 West at 1 pm"}],"uid":"27466","created_gmt":"2016-02-15 10:03:04","changed_gmt":"2017-04-13 21:16:39","author":"Dani Denton","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-02-29T12:00:00-05:00","event_time_end":"2016-02-29T13:00:00-05:00","event_time_end_last":"2016-02-29T13:00:00-05:00","gmt_time_start":"2016-02-29 17:00:00","gmt_time_end":"2016-02-29 18:00:00","gmt_time_end_last":"2016-02-29 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"},{"id":"47223","name":"College of Computing"},{"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":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EDani Denton\u003Cbr \/\u003Edenton at cc dot gatech dot edu\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}