We introduce the notion of t-sum of squares (sos) submodularity, which is a hierarchy, indexed by t, of sufficient algebraic conditions for certifying submodularity of set functions. We show that, for fixed t, each level of the hierarchy can be verified via a semidefinite program of size polynomial in n, the size of the ground set of the set function. This is particularly relevant given existing hardness results around testing whether a set function is submodular (Crama, 1989). We derive several equivalent algebraic characterizations of t-sos submodularity and identify submodularity-preserving operations that also preserve t-sos submodularity. We further present a complete classification of the cases for which submodularity and t-sos submodularity coincide, as well as examples of t-sos-submodular functions. We demonstrate the usefulness of t-sos submodularity through three applications: (i) a new convex approach to submodular regression, involving minimal manual tuning; (ii) a systematic procedure to derive lower bounds on the submodularity ratio in approximate submodular maximization, and (iii) improved difference-of-submodular decompositions for difference-of-submodular optimization.

This is joint work with Anna Deza (Georgia Tech).