{"593876":{"#nid":"593876","#data":{"type":"event","title":"ARC Colloquium: Deeparnab Chakrabarty (Dartmouth)","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\u003EDeeparnab Chakrabarty (Dartmouth)\u003C\/strong\u003E\u003C\/p\u003E\r\n\r\n\u003Cp align=\u0022center\u0022\u003E\u003Cstrong\u003EFriday, August\u0026nbsp;4, 2017\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\u003Cstrong\u003ETitle:\u0026nbsp;\u003C\/strong\u003ESubmodular Function Minimization via Continuous Optimization\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESubmodular functions are beautiful objects arising in many areas including computer science, probability, operations research, etc.\u0026nbsp; They are set functions defined over subsets of an n-element universe with the property that f(A) + f(B) is at least f(union of A and B) + f(intersection of A and B). One paradigmatic problem is that of submodular function minimization: find the set which minimizes f with only oracle access to f. Amazingly, this can be done in polynomial time.\u0026nbsp; Recently, continuous optimization techniques have given rise to fast algorithms for submodular function minimization (SFM).\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EA large part of the talk will be survey-ish, and time permitting I will talk about some recent results of mine in this line.\u0026nbsp; The new results are joint work with Prateek Jain, Pravesh Kothari, Yin Tat Lee, Aaron Sidford, and Sam Wong.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E----------------------------------------------------------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.cs.dartmouth.edu\/~deepc\/\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: \u003Ca href=\u0022https:\/\/smartech.gatech.edu\/handle\/1853\/46836\u0022\u003Ehttps:\/\/smartech.gatech.edu\/handle\/1853\/46836\u003C\/a\u003E\u003C\/em\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cem\u003E\u003Ca href=\u0022https:\/\/mailman.cc.gatech.edu\/mailman\/listinfo\/arc-colloq\u0022\u003EClick here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu \u003C\/a\u003E\u003C\/em\u003E\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Submodular Function Minimization via Continuous Optimization (Klaus 1116E at 11am)"}],"uid":"32895","created_gmt":"2017-08-01 14:06:32","changed_gmt":"2017-08-01 14:06:32","author":"Eric Vigoda","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-08-04T12:00:00-04:00","event_time_end":"2017-08-04T13:00:00-04:00","event_time_end_last":"2017-08-04T13:00:00-04:00","gmt_time_start":"2017-08-04 16:00:00","gmt_time_end":"2017-08-04 17:00:00","gmt_time_end_last":"2017-08-04 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":"78771","name":"Public"},{"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":""}}}