An Exponential Value-Oracle Lower Bound for \({k}\)-Submodular Function Minimization
Abstract. We give a simple family of [Formula: see text]-submodular functions for every fixed [Formula: see text], showing that minimization in the value-oracle model requires exponentially many oracle queries.