{"648989":{"#nid":"648989","#data":{"type":"event","title":"ARC Colloquium: Anupam Gupta (CMU)","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\u003EAnupam Gupta (CMU)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EMonday, October 18, 2021\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align = \u0022center\u0022\u003E\u003Cstrong\u003EKlaus 1116 East - 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:\u0026nbsp; \u003C\/strong\u003E Finding and Counting k-cuts in Graphs\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract: \u003C\/strong\u003EFor an undirected graph with edge weights, a k-cut is a set of edges whose deletion breaks the graph into at least k connected components. How fast can we find a minimum-weight k-cut? And how many minimum k-cuts can a graph have? The two problems are closely linked. In 1996 Karger and Stein showed how to find a minimum k-cut in approximately n^{2k-2} time; their proof also bounded the number of minimum k-cuts by n^{2k-2}, using the probabilistic method. Prior\u0026nbsp;to our work, these were the best results known. Moreover, both these\u0026nbsp;results were not known to be tight, except for the case of k=2 (which is the classical problem of finding graph min-cuts).\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this talk, we show how both these results can be improved to approximately n^k. We discuss how extremal bounds for set systems, plus a refined analysis of the Karger\u0026#39;s contraction algorithm, can give near-optimal bounds.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThis is joint work with Euiwoong Lee (U.Michigan), Jason Li (CMU), and David Harris (Maryland).\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022https:\/\/csd.cmu.edu\/people\/faculty\/anupam-gupta\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\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":"Finding and Counting k-cuts in Graphs - Klaus 1116 East at 11am"}],"uid":"27544","created_gmt":"2021-07-22 15:20:37","changed_gmt":"2021-09-24 13:04:43","author":"Francella Tonge","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2021-10-18T12:00:00-04:00","event_time_end":"2021-10-18T13:00:00-04:00","event_time_end_last":"2021-10-18T13:00:00-04:00","gmt_time_start":"2021-10-18 16:00:00","gmt_time_end":"2021-10-18 17:00:00","gmt_time_end_last":"2021-10-18 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":""}}}