{"660244":{"#nid":"660244","#data":{"type":"event","title":"ARC Colloquium: Sanjeev Khanna (University of Pennsylvania)","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\u003ESanjeev Khanna (University of Pennsylvania)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003ESeptember 19, 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\u003Cstrong\u003ETitle:\u003C\/strong\u003E On Regularity Lemma and Barriers in Streaming and Dynamic Matching\u003Cstrong\u003E \u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract:\u0026nbsp;\u0026nbsp;\u003C\/strong\u003EWe present a new approach for finding matchings in dense graphs by building on Szemeredi\u0026#39;s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit (very) slight improvements over long standing bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for $n$-vertex graphs:\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E(a) A single-pass streaming algorithm that finds a near-optimal matching in $o(n^2)$ bits of space. This constitutes the first single-pass, sublinear-space algorithm that improves over the trivial $1\/2$-approximation of the greedy algorithm.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E(b) A fully dynamic algorithm that with high probability maintains a near-optimal matching in $o(n)$ worst-case update time per edge update, improving upon the previous best update time. The algorithm works even against an adaptive adversary.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe key idea behind both these results is to maintain a matching cover which is a \u0026ldquo;sparse\u0026rdquo; subgraph that approximately preserves matchings in each induced subgraph of the input graph. However, given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some function of $(log* n)$. Nevertheless, these results show that the \u0026ldquo;right\u0026rdquo; answer to these problems is not what is dictated by the previous bounds.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThis is joint work with Sepehr Assadi, Soheil Behnezhad, and Huan Li.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E---------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/www.cis.upenn.edu\/~sanjeev\/\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":"On Regularity Lemma and Barriers in Streaming and Dynamic Matching -  Klaus 1116 at 11am"}],"uid":"35702","created_gmt":"2022-08-17 13:55:15","changed_gmt":"2022-09-06 17:29:41","author":"mb121","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2022-09-19T12:00:00-04:00","event_time_end":"2022-09-19T13:00:00-04:00","event_time_end_last":"2022-09-19T13:00:00-04:00","gmt_time_start":"2022-09-19 16:00:00","gmt_time_end":"2022-09-19 17:00:00","gmt_time_end_last":"2022-09-19 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":""}}}