{"660030":{"#nid":"660030","#data":{"type":"event","title":"ARC Colloquium: Jan van den Brand (Georgia Tech)","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\u003EJan van den Brand (Georgia Tech)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EAugust 29, 2022\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 - 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 Fully Dynamic st-Distances \u003Cstrong\u003E \u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EIn this talk I will present a fully dynamic algorithm for maintaining approximate distances in a graph.\u003Cbr \/\u003E\r\nIn particular, given an unweighted and undirected graph G=(V,E) undergoing edge insertions and deletions, two vertices s,t and a parameter 0\u0026lt;\u03f5\u0026le;1, the dynamic algorithm maintains a (1+\u03f5)-approximation of the st-distance\u0026nbsp; in O(n1.407) time per update (for the current best known bound on the matrix multiplication exponent \u0026omega;).\u003Cbr \/\u003E\r\nAt the core, the approach is to combine algebraic data structures with a graph theoretic technique called emulators. This also leads to novel dynamic algorithms for maintaining (1+\u03f5,\u0026beta;)-emulators that improve upon the state of the art.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.ocf.berkeley.edu\/~vdbrand\/\u0022\u003ESpeaker\u0026#39;s Webpage\u003C\/a\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\u003Cem\u003E and \u003Ca href=\u0022http:\/\/arc.gatech.edu\/node\/121\u0022\u003Ehttp:\/\/arc.gatech.edu\/node\/121\u003C\/a\u003E \u003C\/em\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@Klauscc.gatech.edu\u003C\/em\u003E\u003C\/a\u003E\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Fully Dynamic st-Distances - Klaus 1116 at 11am"}],"uid":"27544","created_gmt":"2022-08-09 17:58:53","changed_gmt":"2022-08-22 12:18:06","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2022-08-29T12:00:00-04:00","event_time_end":"2022-08-29T13:00:00-04:00","event_time_end_last":"2022-08-29T13:00:00-04:00","gmt_time_start":"2022-08-29 16:00:00","gmt_time_end":"2022-08-29 17:00:00","gmt_time_end_last":"2022-08-29 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":"177814","name":"Postdoc"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}