*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
Deeparnab Chakrabarty (Dartmouth)
Friday, August 4, 2017
Klaus 1116 East - 11:00 am
Title: Submodular Function Minimization via Continuous Optimization
Abstract:
Submodular functions are beautiful objects arising in many areas including computer science, probability, operations research, etc. 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. Recently, continuous optimization techniques have given rise to fast algorithms for submodular function minimization (SFM).
A large part of the talk will be survey-ish, and time permitting I will talk about some recent results of mine in this line. The new results are joint work with Prateek Jain, Pravesh Kothari, Yin Tat Lee, Aaron Sidford, and Sam Wong.
----------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
