Symmetric Submodular Minimization from Comparisons

James Fox, David P. Woodruff

Given value-oracle access to a symmetric submodular function $f:2^V\to \mathbb{R}$ with $|V|=n$, a nontrivial minimizer can be found using $O(n^3)$ value queries. We study the weake…