Sum of Squares Submodularity

Anna Deza, Georgina Hall

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 func…