2 papers
math.OC2026
Sum of Squares Submodularity
Anna Deza, Georgina Hall
We introduce the notion of -sum of squares (sos) submodularity, which is a hierarchy, indexed by , of sufficient algebraic conditions for certifying submodularity of set func…
math.OC2026
On Approximate Computation of Critical Points
Amir Ali Ahmadi, Georgina Hall
We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a…