New Query Lower Bounds for Submodular Function MInimization

We consider submodular function minimization in the oracle model: given black-box access to a submodular set function $f:2^{[n]}\rightarrow $\mathbb{R}$$,findanelementof$\arg\min_S {f(S)}$usingasfewqueriesto$f(\cdot)$aspossible\mathrm{.}State-of-the-artalgorithmssucceedwith$\tilde{O}(n^2)$ queries [LeeSW15], yet the best-known lower bound has never been improved beyond $n$ [Harvey08]. We provide a query lower bound of $2n$ for submodular function minimization, a $3n\mathrm{/}2-2$ query lower bound for the non-trivial minimizer of a symmetric submodular function, and a $\left(\genfrac{}{}{0px}{}{n}{2}\right)$ query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our $3n\mathrm{/}2-2$ lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a $3n\mathrm{/}2-2$ cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than $n+1$ for $s$-$t$ mincut, even in a directed, weighted graph.