Deeparnab Chakrabarty: Parallel Submodular Function Minimization

PASSCODE: 430018

Submodular functions are fundamental objects in discrete optimization arising in various areas from computer science to economics. They are set functions which prescribe a value to every subset of an n-element universe, and are defined “locally” as follows: for every subset A of the universe and elements i & j not in A, f(A) + f(A + i + j) is at most f(A+i) + f(A+j). This property alone leads to tractability of many optimization problems: a remarkable one among them is that submodular function minimization (SFM), that is, finding the global minima of such set functions, can be done using polynomially many queries.
In this talk, we will mainly focus on “lower bounds” or the “limitations of locality”. Most of the talk will be about recent works on the *parallel complexity* of SFM: how many *rounds* of queries are needed for efficient SFM? Can this be done with only constant or logarithmic rounds? The answer is “no”, and we will describe some constructions and quantify this. We will also discuss some questions left open by these works.

This talk is based on joint works with Yu Chen, Andrei Graur, Haotian Jiang, Sanjeev Khanna, and Aaron Sidford