preprint · arXiv (Cornell University) · 2025

Sum of Squares Submodularity

Deza, Anna, Hall, Georgina

Cited by 0Open access

Abstract

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. Overall, our work builds a new bridge between discrete optimization and real algebraic geometry by connecting sum of squares-based algebraic certificates to a fundamental discrete structure, submodularity.

Cite this paper

APA 7

Deza, A., & Hall, G. (2025). Sum of Squares Submodularity. arXiv (Cornell University). https://doi.org/10.48550/arxiv.2510.24550

MLA 9

Deza, Anna, and Georgina Hall. “Sum of Squares Submodularity.” arXiv (Cornell University), 2025, https://doi.org/10.48550/arxiv.2510.24550.

Chicago

Deza, Anna, and Georgina Hall. 2025. “Sum of Squares Submodularity.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.2510.24550.

Harvard

Deza, A. and Hall, G. (2025) ‘Sum of Squares Submodularity’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.2510.24550.

BibTeX

@misc{deza2025squares,
  title = {{Sum of Squares Submodularity}},
  author = {Deza, Anna and Hall, Georgina},
  journal = {arXiv (Cornell University)},
  year = {2025},
  doi = {10.48550/arxiv.2510.24550}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.