A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization

Submodular function minimization (SFM) and matroid intersection are fundamental discrete optimization problems with applications in many fields. It is well known that both of these can be solved making poly(N ) queries to a relevant oracle (evaluation oracle for SFM and rank oracle for matroid intersection), where N denotes the universe size. However, all known polynomial query algorithms are highly adaptive, requiring at least N rounds of querying the oracle. A natural question is whether these can be efficiently solved in a highly parallel manner, namely, with poly(N ) queries using only poly-logarithmic rounds of adaptivity.

An important step towards understanding the adaptivity needed for efficient parallel SFM was taken recently in the work of Balkanski and Singer who showed that any SFM algorithm making poly(N ) queries necessarily requires Ω(log N/ log log N ) rounds. This left open the possibility of efficient SFM algorithms in poly-logarithmic rounds. For matroid intersection, even the possibility of a constant round, poly(N ) query algorithm was not hitherto ruled out.

In this work, we prove that any, possibly randomized, algorithm for submodular function minimization or matroid intersection making poly(N ) queries requires 1 Ω N 1/3 rounds of adaptivity. In fact, we show a polynomial lower bound on the number of rounds of adaptivity even for algorithms that make at most 2 N 1-δ queries, for any constant δ > 0. Therefore, even though SFM and matroid intersection are efficiently solvable, they are not highly parallelizable in the oracle model.