  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 $n^{O(M)}$ and the second method has depth $\widetilde{O}(n^{1/3}
M^{2/3})$ and query complexity $O(\mathrm{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 $\ell_2$-Lipschitz
functions. Interestingly, to obtain our second result we provide the first
highly-parallel algorithm for minimizing $\ell_\infty$-Lipschitz function over
the hypercube which obtains near-optimal depth for obtaining constant accuracy.
