{"id":5,"date":"2025-03-10T08:04:37","date_gmt":"2025-03-10T08:04:37","guid":{"rendered":"https:\/\/taaresearchlunch.univie.ac.at\/?p=5"},"modified":"2025-03-10T13:06:20","modified_gmt":"2025-03-10T13:06:20","slug":"13-march-2025-peter-kiss","status":"publish","type":"post","link":"https:\/\/taaresearchlunch.univie.ac.at\/?p=5","title":{"rendered":"13 March 2025 &#8211; Peter Kiss"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\"><strong>Date:<\/strong> 13 March 2025<br><strong>Time:<\/strong> 11:45 &#8211; 12:45<br><strong>Location: <\/strong>Forschungslabor 3 (sofa room)<\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Speaker:<\/strong> <a href=\"https:\/\/sites.google.com\/view\/peterkiss\/home\">Peter Kiss<\/a><br><strong>Title:<\/strong> <a href=\"https:\/\/arxiv.org\/abs\/2302.05030\">Dynamic (1+\u03b5)-Approximate Matching Size in Truly Sublinear Update Time<\/a><\/p>\n\n\n\n<p class=\"wp-block-paragraph\"><strong>Abstract:<\/strong><br>We show a fully dynamic algorithm for maintaining (1+\u03b5)-approximate <em>size<\/em> of maximum matching of the graph with n vertices and m edges using m<sup>0.5\u2212\u03a9<sub>\u03b5<\/sub>(1)<\/sup> update time. This is the first polynomial improvement over the long-standing O(n) update time, which can be trivially obtained by periodic recomputation. Thus, we resolve the value version of a major open question of the dynamic graph algorithms literature (see, e.g., [Gupta and Peng FOCS&#8217;13], [Bernstein and Stein SODA&#8217;16], [Behnezhad and Khanna SODA&#8217;22]). Our key technical component is the first sublinear algorithm for (1,\u03b5n)-approximate maximum matching with sublinear running time on dense graphs. All previous algorithms suffered a multiplicative approximation factor of at least 1.499 or assumed that the graph has a very small maximum degree.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Date: 13 March 2025Time: 11:45 &#8211; 12:45Location: Forschungslabor 3 (sofa room) Speaker: Peter KissTitle: Dynamic (1+\u03b5)-Approximate Matching Size in Truly Sublinear Update Time Abstract:We show a&#46;&#46;&#46;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[2],"class_list":["post-5","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-talks"],"_links":{"self":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/5","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=5"}],"version-history":[{"count":5,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/5\/revisions"}],"predecessor-version":[{"id":22,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=\/wp\/v2\/posts\/5\/revisions\/22"}],"wp:attachment":[{"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=5"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=5"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/taaresearchlunch.univie.ac.at\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=5"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}