A lower bound for parallel submodular minimization

In this paper, we study submodular function minimization in the adaptive complexity model. Seminal work by Gr'otschel, Lovász, and Schrijver shows that with oracle access to a function f, the problem of submodular minimization can be solved exactly with poly(n) queries to f. A long line of work has since then been dedicated to the acceleration of submodular minimization. In particular, recent work obtains a (strongly) polynomial time algorithm with Õ(n 3) query complexity. A natural way to accelerate computation is via parallelization, though very little is known about the extent to which submodular minimization can be parallelized.