Testing submodularity and other properties of valuation functions

Eric Blais, Abhinav Bommireddi

We show that for any constant $\epsilon >0$ and $p\ge 1$, it is possible to distinguish functions $f:\{0,1{\}}^n\to [0,1]$ that are submodular from those that are $\epsilon$-far from every sub…