  We provide a generic technique for constructing families of submodular
functions to obtain lower bounds for submodular function minimization (SFM).
Applying this technique, we prove that any deterministic SFM algorithm on a
ground set of $n$ elements requires at least $\Omega(n \log n)$ queries to an
evaluation oracle. This is the first super-linear query complexity lower bound
for SFM and improves upon the previous best lower bound of $2n$ given by [Graur
et al., ITCS 2020]. Using our construction, we also prove that any (possibly
randomized) parallel SFM algorithm, which can make up to $\mathsf{poly}(n)$
queries per round, requires at least $\Omega(n / \log n)$ rounds to minimize a
submodular function. This improves upon the previous best lower bound of
$\tilde{\Omega}(n^{1/3})$ rounds due to [Chakrabarty et al., FOCS 2021], and
settles the parallel complexity of query-efficient SFM up to logarithmic
factors due to a recent advance in [Jiang, SODA 2021].
