  We consider submodular function minimization in the oracle model: given
black-box access to a submodular set function $f:2^{[n]}\rightarrow
\mathbb{R}$, find an element of $\arg\min_S \{f(S)\}$ using as few queries to
$f(\cdot)$ as possible. State-of-the-art algorithms succeed with
$\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/2-2$ query lower bound for the non-trivial minimizer of a symmetric
submodular function, and a $\binom{n}{2}$ query lower bound for the non-trivial
minimizer of an asymmetric submodular function.
  Our $3n/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/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.
