New Query Lower Bounds for Submodular Function MInimization

Andrei Graur, Tristan Pollner, Vidhya Ramaswamy +1

We consider submodular function minimization in the oracle model: given black-box access to a submodular set function $f:2^{[n]}\to \mathbb{R}$, find an element of $\arg\mi…