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


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:

Click here to subscribe to the seminar email list:

Event Details


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