ARC Colloquium: Deeparnab Chakrabarty (Dartmouth)

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.

----------------------------------------------------------------

Speaker's webpage

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

Event Details

Date/Time:

  • Friday, August 4, 2017
    11:00 am - 12:00 pm
Location: Klaus 1116 East