Parallel Submodular Function Minimization

We consider the parallel complexity of submodular function minimization (SFM). We provide a pair of methods which obtain two new query versus depth trade-offs a submodular function defined on subsets of n elements that has integer values between -M and M. The first method has depth 2 and query complexity nO(M) and the second method has depth widetildeO(n1/3 M2/3) and query complexity O(poly(n, M)). Despite a line of work on improved parallel lower bounds for SFM, prior to our work the only known algorithms for parallel SFM either followed from more general methods for sequential SFM or highly-parallel minimization of convex ℓ2-Lipschitz functions. Interestingly, to obtain our second result we provide the first highly-parallel algorithm for minimizing ℓ_∞-Lipschitz function over the hypercube which obtains near-optimal depth for obtaining constant accuracy.