Pith. sign in

REVIEW 3 major objections 5 minor 59 references

Sum of Squares Submodularity

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every submodular function of degree $d$ carries a sum-of-squares certificate of submodularity at level $t = \lceil (n+d-5)/2 \rceil$, and every fixed level of the certificate hierarchy is checkable by a semidefinite program.

desk verdict New sos hierarchy for submodularity with a real exactness gap: the core idea is good, but the proof of exactness rests on unstated external bounds and an unproven extension. read the letter →

arxiv 2510.24550 v2 pith:MTMDG2KA submitted 2025-10-28 math.OC math.AGmath.FA

Anna Deza , Georgina Hall This is my paper · ORCID
classification math.OCmath.AGmath.FA MSC 90C2290C2713P10
keywords submodularitysumofsquarespolynomialssemidefiniteprogrammingsetfunctionsmultilinearextensiont-sossubmodularregressionratio
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces $t$-sos submodularity, a hierarchy indexed by $t$ of sufficient algebraic conditions for a set function to be submodular. For fixed $t$, membership in the hierarchy is checked by a semidefinite program of size polynomial in $n$, the size of the ground set—this matters because deciding submodularity itself is NP-hard for set functions of degree at least 4. The paper proves the hierarchy is finite and exact: at $t = \left\lceil \frac{n+d-5}{2} \right\rceil$, the $t$-sos-submodular functions of degree $d$ are exactly the submodular functions of degree $d$, so every submodular function has a sum-of-squares certificate. It also gives equivalent algebraic forms of the hierarchy, classifies the small-degree cases, and demonstrates the hierarchy on submodular regression, lower bounds for approximate submodular maximization, and difference-of-submodular optimization.

What carries the argument

The key object is the hierarchy itself, defined through the quotient ring of the Boolean cube: $-\partial^2 F / \partial x_i \partial x_j \equiv \sum_r q_r(x_{-i,j})^2 \pmod{I_2[x_{-i,j}]}$, with $\deg q_r \le t$. The ideal $I_2 = \langle x_i^2 - x_i \rangle$ encodes the fact that variables sit in $\{0,1\}$, so the congruence turns a nonnegativity condition on the cube into an explicit certificate. The paper pairs this with telescoping identities—for example $\partial F(x)/\partial x_i - \partial F(y)/\partial x_i = \sum_{j \neq i} (y_j - x_j)(-\partial^2 F / \partial x_i \partial x_j)([xy]^j)$—that transfer the second-order certificate to every other classical formulation of submodularity, using auxiliary ideals $I_1[x,y]$ and $I_0[x,y,s]$ that encode $x \le y$ and $(x,y,x \circ y)$. The Gram-matrix SDP representation over square-free monomials $z_t^T Q z_t$ is what makes each level computationally checkable, and the degree bounds from the telescoping identities are what set the top exactness level.

What would settle it

Run the feasibility SDP from Proposition 11 on the degree-4 example in Proposition 27 at $t = \lceil (n-2)/2 \rceil - 1$ and at $t = \lceil (n-2)/2 \rceil$; the first must be infeasible and the second feasible, and any other outcome would refute the claimed gap—or exhibit any submodular degree-$d$ function whose negative cross-derivative is nonnegative on the cube yet is not $t$-sos with $t = \lceil (n+d-5)/2 \rceil$, which would directly falsify Proposition 12.

Watch

Extended reading notes

Core claim

The paper's central discovery is that diminishing returns can be certified by algebra: a set function with multilinear extension $F$ is $t$-sos-submodular when, for every pair $i \neq j$, the polynomial $-\partial^2 F / \partial x_i \partial x_j$ is a sum of squares of polynomials of degree at most $t$ modulo the ideal $I_2[x_{-i,j}]$, which defines the Boolean cube. Any such function is submodular, because a sum of squares is nonnegative on the cube; and for fixed $t$ the condition is an SDP feasibility problem with $\frac{n(n-1)}{2}$ constraints of size $\sum_{k=0}^{t} \binom{n-2}{k}$. The exactness statement is that for $t < \lceil (d-2)/2 \rceil$ no degree-$d$ function can be $t$-sos-submodular, while at $t = \lceil (n+d-5)/2 \rceil$ every submodular function of degree $d$ is $t$-sos-submodular. Hence the hierarchy interpolates from a cheap sufficient test to a complete characterization, and its intermediate levels give tunable algebraic certificates of submodularity.

Load-bearing premise

The argument that the hierarchy becomes exact at the top level depends on an outside theorem, cited but not proved here, about how many squared terms are needed to express any nonnegative function on a 0/1 grid as a sum of squares; if that degree bound fails, the hierarchy may stop short of submodularity.

Editorial extensions

If this is right

  • For every fixed level $t$, certifying $t$-sos submodularity is a semidefinite program with $n(n-1)/2$ constraints of size $\sum_{k=0}^{t}\binom{n-2}{k}$; at constant $t$ this is polynomial in $n$, so submodularity becomes efficiently certifiable rather than merely decidable.
  • Submodular functions of degree 1, 2, and 3 are certified at levels 0, 0, and 1 respectively, so the easy polynomial-time cases of the hardness dichotomy are fully explained by the hierarchy.
  • The degree-4 example proves the hierarchy can require $t = O(n)$ in the worst case, so any SDP-based certificate for high-degree functions can be exponential in $n$, matching the NP-hardness of the original test.
  • Solving the regression SDP always returns a submodular polynomial regressor, turning shape-constrained regression into a convex problem with only two tuning parameters, degree $k$ and level $t$.
  • The SDP in Corollary 35 yields systematic lower bounds on the submodularity ratio $\gamma^*$, recovering or improving the spectral bound on a determinantal example.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: The exactness threshold is a worst-case statement. Random submodular functions of degree $d \ge 4$ may typically admit certificates at level $O(d)$, and a numerical experiment scanning random quartics for the smallest feasible $t$ would indicate whether the practical hierarchy is much shallower than the theoretical $O(n)$ ceiling.
  • Inference: Because each certificate is an explicit Gram matrix, the hierarchy could serve as a witness system for submodularity in applications where a third party must verify the property without re-running an optimization; the paper does not discuss this verification use.
  • Inference: The same quotient-ideal machinery applies to any finite variety defined by coordinate equations, so one can define analogous hierarchies for other discrete convexity notions on grids or lattices; the exactness level would plausibly again be about half the dimension plus half the degree, and testing that on L-convex functions is a direct extension.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces t-sos submodularity, a hierarchy of sufficient algebraic conditions for submodularity of set functions, defined by requiring that each second partial derivative of the multilinear extension, negated, be a sum of squares modulo the hypercube ideal on the remaining variables. The authors prove that every t-sos-submodular function is submodular (Proposition 10), that membership is checkable by an SDP of polynomial size in n for fixed t (Proposition 11), and that for large t the hierarchy becomes exact (Proposition 12). They give equivalent algebraic characterizations via the other standard definitions of submodularity (Theorems 14-19), study operations preserving t-sos submodularity, and analyze the gap between submodularity and t-sos submodularity, including degree-3 positive results and a degree-4 example requiring large t. Three applications are presented: submodular regression via SDP, lower bounds on the submodularity ratio, and improved difference-of-submodular decompositions, each with numerical experiments.

Significance. If the main claims hold, this paper provides a new connection between discrete optimization and real algebraic geometry, giving a systematic, SDP-based sufficient condition for submodularity that is exact at a finite level. The constructive proofs of the equivalence theorems, the explicit SDP sizes, and the numerical demonstrations of the regression and submodularity-ratio applications are genuine strengths. The paper supplies detailed proofs for the equivalence theorems and for the gap examples, and the SDP formulations are explicit, which supports reproducibility of the theoretical results.

major comments (3)
  1. [Section 3.4, Appendix A.2, Proposition 12] Proposition 12's exactness direction, namely that every submodular function of degree d is t-sos-submodular for t = ceil((n+d-5)/2), is load-bearing for the paper's central claim that the hierarchy is a complete algebraic certificate at a finite level. The proof in Appendix A.2 delegates this direction to 'the main result of (Sakaue et al., 2016)' without stating the theorem, its hypotheses, or the exact degree bound. As written, the reader cannot verify that the bound for a polynomial of degree d-2 in n-2 variables is exactly ceil((n+d-5)/2) rather than, say, ceil((n+d-4)/2); if the external bound is larger, the stated threshold is wrong. The sentence in the proof saying 'for t at most ceil((n+d-5)/2)' is also ambiguous, since the hierarchy is nested and one would expect 'at least' or 'equal to'. Please state the external result precisely, verify that its hypotheses hold for the quotients by I2[x_{-i,j}], and show that it yields exactly the claimed threshold.
  2. [Section 4.2, Corollary 35] Corollary 35 asserts gamma*(f) = gamma^t_sos for t = ceil((n+d-1)/2), which is the basis for the submodularity-ratio bounds in Section 4.2. The proof is only 'by using similar proof techniques to Propositions 10, 11 and 12.' However, the condition in (4) requires t-sos modulo I1[x,y], whose variety {(x,y) in {0,1}^{2n} : x <= y} is not a Boolean hypercube; it is a product of three-point fibers. The representation bound from (Sakaue et al., 2016), as invoked in Proposition 12, applies to the hypercube, and no argument is given for how it transfers to this non-hypercube variety. Since this equality is used to interpret the numerical lower bounds on gamma*, it needs a self-contained proof or a reference with the theorem statement and a verification that its hypotheses hold for I1[x,y].
  3. [Section 4.3, after equation (10)] The sentence 'It can further be shown that the decomposition (G*,H*) obtained is t-sos-submodular-irreducible' is an assertion without proof. This property is used to justify that solving (10) yields a meaningful decomposition for the submodular-supermodular procedure, so the claim should be either proved or explicitly marked as a conjecture. Relatedly, the uniqueness assertion in the footnote to Proposition 31 ('We place ourselves in a regime where m is large enough so that the problem is guaranteed to have a unique solution') is not supported; the SDP (3) does not obviously have a unique solution, and the needed condition on m is not stated.
minor comments (5)
  1. [Section 2.2, Proposition 3] The proof of Proposition 3 is omitted and the text says it is 'ommitted' (typo). Given that several of the algebraic characterizations (iv')-(vii') are described as new, it would be helpful to include the translation or at least a reference, even in an appendix.
  2. [Section 3.4, Proposition 26] The paragraph after Proposition 26 claims that the appendix proof 'further shows that in the degree-3 setting, one can reduce the semidefinite program under consideration to a linear program,' but the appendix proof only gives an explicit 1-sos decomposition and does not discuss an LP reduction.
  3. [Section 4.2, text near Figure 2] The sentence 'our method provides an improved upper bound on gamma*' should read 'lower bound', since gamma^t_sos is a lower bound on gamma* in the described setting.
  4. [Section 4.3, proofs of Propositions 39 and 41] The proof of Proposition 41 has a typo in the objective (missing second-derivative symbol), and the proof of Proposition 39 contains a typo '(h’ - p’ )π' that should be '(h′−p)π'. These should be corrected for readability.
  5. [References] The reference list includes (Sakaue et al., 2016) as an ICCOPT proceedings article; since the paper relies on its main theorem for the central exactness claim, the authors should state the theorem explicitly to make the manuscript self-contained.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the exactness claims rest on an independent external SOS bound, not on fitted inputs or self-referential definitions.

full rationale

The paper's central derivation is not circular. Definition 9 defines t-sos submodularity directly as the requirement that each second derivative -d2F/dxi dxj be t-sos modulo I2[x_{-i,j}], while submodularity is independently characterized by nonnegativity of those same derivatives on {0,1}^n (Proposition 3(iii')). Proposition 10 is the soundness of the SOS certificate, not a restatement of the target. The converse/exactness claim in Proposition 12 is delegated to the main result of Sakaue et al. (2016), an external result by non-overlapping authors; the paper neither fits parameters to the data nor renames a fitted quantity as a prediction. The applications in Section 4 use the hierarchy as a tractable constraint set and compare against external baselines (FlexSubNet, spectral bounds, trivial DS decompositions), so no fitted input is called a prediction. The genuine weaknesses are support gaps, not circularity: the Sakaue bound is not stated in the paper, Corollary 35 asserts the equality gamma* = gamma^t_sos for t = ceil((n+d-1)/2) 'by using similar proof techniques' without proof, and Section 4.3 states that the optimal solution to (10) is t-sos-submodular-irreducible with 'It can further be shown' and no proof. These omissions affect correctness risk but do not make any derivation equivalent to its inputs by construction. The only self-citation (Ahmadi and Hall 2018, Remark 40) is an analogy and is not load-bearing.

Assumptions & free parameters 0 free parameters · 4 assumptions · 2 invented entities

The theoretical core relies on standard real algebraic geometry and the cited representation theorem of Sakaue et al. for exactness at high t. No numerical constants are fitted to data in the derivation of the hierarchy; the three applications involve hyperparameters (k, t, lambda) but these are not load-bearing for the theoretical claims.

assumptions (4)
  • domain assumption The seven conditions in Definition 1 and Proposition 3 are equivalent to submodularity, including the algebraic translations (i')-(vii').
    The paper states the translation is 'straightforward' and omits the proof. These equivalences underlie the definition of t-sos submodularity and the characterizations in Section 3.2.
  • domain assumption Sakaue et al. (2016): every polynomial nonnegative on the Boolean hypercube is representable as a sum of squares modulo the hypercube ideal with a degree bound of roughly ceil((m+d)/2).
    Invoked in Proposition 12 to show submodular functions are t-sos for large t and in Corollary 35 for exactness at high t. The theorem is not stated in the paper.
  • standard math The generators of I2, I1, I0 form reduced Grobner bases under the specified monomial order (Proposition 46).
    Used to justify normal form arguments in the proofs of the algebraic equivalences. The paper gives only a sketch: 'This is straightforward to show'.
  • standard math Crama and Hammer Theorem 13.8: for multilinear F, the interval conditions on [0,1]^n are equivalent to the discrete conditions on {0,1}^n in the sense of Remark 4.
    Cited in Remark 4 to justify that working on {0,1}^n does not lose generality for the continuous equivalents.
invented entities (2)
  • t-sos submodularity
    purpose: A hierarchy of sufficient algebraic conditions for submodularity verifiable by SDP
    New mathematical definition central to the paper. Its value is internal to the framework and it has no external falsifiable handle.
  • The ideals I0[x,y,s] and I1[x,y]
    purpose: Quotient rings used to express algebraic characterizations of t-sos submodularity over the ordered hypercube
    New algebraic constructs introduced specifically for the proofs; their properties are established within the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sum of Squares Submodularity." pith.science (2026). https://pith.science/paper/MTMDG2KA

@misc{pith2026251024550,
  author       = {Pith},
  title        = {Pith review of: Sum of Squares Submodularity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MTMDG2KA}},
  note         = {Machine review of arXiv:2510.24550}
}
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.

Figures

Figures reproduced from arXiv: 2510.24550 by the authors.

Figure 1
Figure 1. Comparison of root mean squared test error for various methods, fitted to noisy [PITH_FULL_IMAGE:figures/full_fig_p014_1.png] view at source ↗
Figure 2
Figure 2. Comparison of γ ∗ , γspectral and γ t,k trunc,sos for different values of k. We remark that our methods could likewise be used to obtain bounds on parameters ap￾pearing in other definitions of approximate submodularity, such as the ones defined in (Horel and Singer, 2016; Krause et al., 2008). 16 [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗
Figure 3
Figure 3. Comparison of root mean squared test error for various methods, fitted to noisy [PITH_FULL_IMAGE:figures/full_fig_p038_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Comparison of average relative optimality gap obtained for ten runs of the [PITH_FULL_IMAGE:figures/full_fig_p040_4.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 51 canonical work pages

  1. [1]

    DC decomposition of nonconvex polynomials with algebraic techniques

    Amir Ali Ahmadi and Georgina Hall. DC decomposition of nonconvex polynomials with algebraic techniques. Mathematical Programming, 169: 0 69--94, 2018

    work page 2018

  2. [2]

    A complete characterization of the gap between convexity and sos-convexity

    Amir Ali Ahmadi and Pablo A Parrilo. A complete characterization of the gap between convexity and sos-convexity. SIAM Journal on Optimization, 23 0 (2): 0 811--833, 2013

    work page 2013

  3. [3]

    NP -hardness of deciding convexity of quartic polynomials and related problems

    Amir Ali Ahmadi, Alex Olshevsky, Pablo A Parrilo, and John N Tsitsiklis. NP -hardness of deciding convexity of quartic polynomials and related problems. Mathematical Programming, 137: 0 453--476, 2013

    work page 2013

  4. [4]

    Submodularity in conic quadratic mixed 0--1 optimization

    Alper Atamt \"u rk and Andr \'e s G \'o mez. Submodularity in conic quadratic mixed 0--1 optimization. Operations Research, 68 0 (2): 0 609--630, 2020

    work page 2020

  5. [5]

    Submodular functions: from discrete to continuous domains

    Francis Bach. Submodular functions: from discrete to continuous domains. Mathematical Programming, 175: 0 419--459, 2019

    work page 2019

  6. [6]

    Learning with submodular functions: A convex optimization perspective

    Francis Bach et al. Learning with submodular functions: A convex optimization perspective. Foundations and Trends in Machine Learning , 6 0 (2-3): 0 145--373, 2013

    work page 2013

  7. [7]

    Learning submodular functions

    Maria-Florina Balcan and Nicholas JA Harvey. Learning submodular functions. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 793--802, 2011

    work page 2011

  8. [8]

    Submodular functions: Learnability, structure, and optimization

    Maria-Florina Balcan and Nicholas JA Harvey. Submodular functions: Learnability, structure, and optimization. SIAM Journal on Computing, 47 0 (3): 0 703--754, 2018

    work page 2018

Show all 59 references
  1. [9]

    Guarantees for greedy maximization of non-submodular functions with applications

    Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In International Conference on Machine Learning, pages 498--507. PMLR, 2017

    2017

  2. [10]

    Continuous submodular function maximization

    Yatao Bian, Joachim M Buhmann, and Andreas Krause. Continuous submodular function maximization. arXiv preprint arXiv:2006.13474, 2020

    2006 arXiv

  3. [11]

    Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions

    Alain Billionnet and Michel Minoux. Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions. Discrete Applied Mathematics, 12 0 (1): 0 1--11, 1985

    1985

  4. [12]

    Submodularity in machine learning and artificial intelligence

    Jeff Bilmes. Submodularity in machine learning and artificial intelligence. arXiv preprint arXiv:2202.00132, 2022

    2022 arXiv

  5. [13]

    Semidefinite O ptimization and C onvex A lgebraic G eometry

    Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas. Semidefinite O ptimization and C onvex A lgebraic G eometry . SIAM, 2012

    2012

  6. [14]

    Undominated DC decompositions of quadratic functions and applications to branch-and-bound approaches

    Immanuel M Bomze and Marco Locatelli. Undominated DC decompositions of quadratic functions and applications to branch-and-bound approaches. Computational Optimization and Applications, 28 0 (2): 0 227--245, 2004

    2004

  7. [15]

    Convex O ptimization

    Stephen P Boyd and Lieven Vandenberghe. Convex O ptimization . Cambridge university press, 2004

    2004

  8. [16]

    Decomposition polyhedra of piecewise linear functions

    Marie-Charlotte Brandenburg, Moritz Grillo, and Christoph Hertrich. Decomposition polyhedra of piecewise linear functions. arXiv preprint arXiv:2410.04907, 2024

    2024 arXiv

  9. [17]

    On the semidefinite representability of continuous quadratic submodular minimization with applications to moment problems

    Samuel Burer and Karthik Natarajan. On the semidefinite representability of continuous quadratic submodular minimization with applications to moment problems. arXiv preprint arXiv:2504.03996, 2025

    2025 arXiv

  10. [18]

    Recognition problems for special classes of polynomials in 0--1 variables

    Yves Crama. Recognition problems for special classes of polynomials in 0--1 variables. Mathematical programming, 44: 0 139--155, 1989

    1989

  11. [19]

    Boolean F unctions: T heory, A lgorithms, and A pplications

    Yves Crama and Peter L Hammer. Boolean F unctions: T heory, A lgorithms, and A pplications . Cambridge University Press, 2011

    2011

  12. [20]

    Shape-constrained regression using sum of squares polynomials

    Mihaela Curmei and Georgina Hall. Shape-constrained regression using sum of squares polynomials. Operations Research, 73 0 (1): 0 543--559, 2025

    2025

  13. [21]

    Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection

    Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19 0 (3): 0 1--34, 2018

    2018

  14. [22]

    Neural estimation of submodular functions with applications to differentiable subset selection

    Abir De and Soumen Chakrabarti. Neural estimation of submodular functions with applications to differentiable subset selection. Advances in Neural Information Processing Systems, 35: 0 19537--19552, 2022

    2022

  15. [23]

    Deep submodular functions: Definitions and learning

    Brian W Dolhansky and Jeff A Bilmes. Deep submodular functions: Definitions and learning. Advances in Neural Information Processing Systems, 29, 2016

    2016

  16. [24]

    Submodular functions, matroids, and certain polyhedra

    Jack Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial Optimization—Eureka, You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, March 5--9, 2001 Revised Papers, pages 11--26. Springer, 2003

    2001

  17. [25]

    Difference of submodular minimization via DC programming

    Marwa El Halabi, George Orfanides, and Tim Hoheisel. Difference of submodular minimization via DC programming. In International Conference on Machine Learning, pages 9172--9201. PMLR, 2023

    2023

  18. [26]

    Sparse sum-of-squares certificates on finite abelian groups

    Hamza Fawzi, James Saunderson, and Pablo A Parrilo. Sparse sum-of-squares certificates on finite abelian groups. In 2015 54th IEEE Conference on Decision and Control (CDC), pages 5909--5914. IEEE, 2015

    2015

  19. [27]

    Optimal bounds on approximation of submodular and xos functions by juntas

    Vitaly Feldman and Jan Vondr \'a k. Optimal bounds on approximation of submodular and xos functions by juntas. SIAM Journal on Computing, 45 0 (3): 0 1129--1170, 2016

    2016

  20. [28]

    Representation, approximation and learning of submodular functions using low-rank decision trees

    Vitaly Feldman, Pravesh Kothari, and Jan Vondr \'a k. Representation, approximation and learning of submodular functions using low-rank decision trees. In Conference on Learning Theory, pages 711--740. PMLR, 2013

    2013

  21. [29]

    Submodular functions in graph theory

    Andr \'a s Frank. Submodular functions in graph theory. Discrete Mathematics, 111 0 (1-3): 0 231--243, 1993

    1993

  22. [30]

    Submodular F unctions and O ptimization , volume 58

    Satoru Fujishige. Submodular F unctions and O ptimization , volume 58. Elsevier, 2005

    2005

  23. [31]

    On the supermodular knapsack problem

    Giorgio Gallo and Bruno Simeone. On the supermodular knapsack problem. Mathematical Programming, 45: 0 295--309, 1989

    1989

  24. [32]

    Approximating submodular functions everywhere

    Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni. Approximating submodular functions everywhere. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 535--544. SIAM, 2009

    2009

  25. [33]

    PEP it: computer-assisted worst-case analyses of first-order optimization methods in python

    Baptiste Goujaud, C \'e line Moucer, Fran c ois Glineur, Julien M Hendrickx, Adrien B Taylor, and Aymeric Dieuleveut. PEP it: computer-assisted worst-case analyses of first-order optimization methods in python. Mathematical Programming Computation, 16 0 (3): 0 337--367, 2024

    2024

  26. [34]

    Equivalent representations of set functions

    Michel Grabisch, Jean-Luc Marichal, and Marc Roubens. Equivalent representations of set functions. Mathematics of Operations Research, 25 0 (2): 0 157--178, 2000

    2000

  27. [35]

    Semidefinite representation of convex sets

    J William Helton and Jiawang Nie. Semidefinite representation of convex sets. Mathematical Programming, 122: 0 21--64, 2010

    2010

  28. [36]

    Maximization of approximately submodular functions

    Thibaut Horel and Yaron Singer. Maximization of approximately submodular functions. Advances in neural information processing systems, 29, 2016

    2016

  29. [37]

    Algorithms for approximate minimization of the difference between submodular functions, with applications

    Rishabh Iyer and Jeff Bilmes. Algorithms for approximate minimization of the difference between submodular functions, with applications. arXiv preprint arXiv:1207.0560, 2012

    2012 arXiv

  30. [38]

    Submodularity beyond submodular energies: coupling edges in graph cuts

    Stefanie Jegelka and Jeff Bilmes. Submodularity beyond submodular energies: coupling edges in graph cuts. In Proc. 2011 IEEE Conf. on Computer Vision and Pattern Recognition, pages 1897--1904. IEEE, 2011

    2011

  31. [39]

    Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies

    Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9 0 (2), 2008

    2008

  32. [40]

    Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope

    Monique Laurent. Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope. Mathematics of operations research, 28 0 (4): 0 871--883, 2003

    2003

  33. [41]

    Sums of squares, moment matrices and optimization over polynomials

    Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging applications of algebraic geometry, pages 157--270. Springer, 2009

    2009

  34. [42]

    Learning mixtures of submodular shells with application to document summarization

    Hui Lin and Jeff A Bilmes. Learning mixtures of submodular shells with application to document summarization. arXiv preprint arXiv:1210.4871, 2012

    2012 arXiv

  35. [43]

    A submodular-supermodular procedure with applications to discriminative structure learning

    Mukund Narasimhan and Jeff Bilmes. A submodular-supermodular procedure with applications to discriminative structure learning. In Proc. 21st Ann. Conf. on Uncertainty in Artificial Intelligence (UAI'05), pages 404--412. AUAI Press, 2005

    2005

  36. [44]

    Submodular F unctions and E lectrical N etworks , volume 54

    Hariharan Narayanan. Submodular F unctions and E lectrical N etworks , volume 54. Elsevier, 1997

    1997

  37. [45]

    An analysis of approximations for maximizing submodular set functions—i

    George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions—i. Mathematical programming, 14: 0 265--294, 1978

    1978

  38. [46]

    Multilinear extensions of games

    Guillermo Owen. Multilinear extensions of games. Management Science, 18 0 (5-part-2): 0 64--79, 1972

    1972

  39. [47]

    Selecting a monomial basis for sums of squares programming over a quotient ring

    Frank Permenter and Pablo A Parrilo. Selecting a monomial basis for sums of squares programming over a quotient ring. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), pages 1871--1876. IEEE, 2012

    2012

  40. [48]

    The quadratic unconstrained binary optimization problem

    Abraham P Punnen. The quadratic unconstrained binary optimization problem. Springer International Publishing, 10: 0 978--3, 2022

    2022

  41. [49]

    Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds

    Maurice Queyranne and Andreas S Schulz. Scheduling unit jobs with compatible release dates on parallel machines with nonstationary speeds. In International Conference on Integer Programming and Combinatorial Optimization, pages 307--320. Springer, 1995

    1995

  42. [50]

    Exact sdp relaxations with truncated moment matrix for binary polynomial optimization problems

    Shinsaku Sakaue, Akiko Takeda, Sunyoung Kim, and Naoki Ito. Exact sdp relaxations with truncated moment matrix for binary polynomial optimization problems. In Proceedings of the 5th International Conference on Continuous Optimization ICCOPT, 2016

    2016

  43. [51]

    A combinatorial algorithm minimizing submodular functions in strongly polynomial time

    Alexander Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Journal of Combinatorial Theory, Series B, 80 0 (2): 0 346--355, 2000

    2000

  44. [52]

    Is submodularity testable? Algorithmica, 69 0 (1): 0 1--25, 2014

    Comandur Seshadhri and Jan Vondr \'a k. Is submodularity testable? Algorithmica, 69 0 (1): 0 1--25, 2014

    2014

  45. [53]

    Large-margin learning of submodular summarization models

    Ruben Sipos, Pannaga Shivaswamy, and Thorsten Joachims. Large-margin learning of submodular summarization models. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 224--233, 2012

    2012

  46. [54]

    Introduction to the T heory of C omputation

    Michael Sipser. Introduction to the T heory of C omputation. ACM Sigact News, 27 0 (1): 0 27--29, 1996

    1996

  47. [55]

    Learning F ourier sparse set functions

    Peter Stobbe and Andreas Krause. Learning F ourier sparse set functions. In Artificial Intelligence and Statistics, pages 1125--1133. PMLR, 2012

    2012

  48. [56]

    Minimizing a submodular function on a lattice

    Donald M Topkis. Minimizing a submodular function on a lattice. Operations research, 26 0 (2): 0 305--321, 1978

    1978

  49. [57]

    Supermodularity and C omplementarity

    Donald M Topkis. Supermodularity and C omplementarity . Princeton university press, 1998

    1998

  50. [58]

    Learning mixtures of submodular functions for image collection summarization

    Sebastian Tschiatschek, Rishabh K Iyer, Haochen Wei, and Jeff A Bilmes. Learning mixtures of submodular functions for image collection summarization. Advances in neural information processing systems, 27, 2014

    2014

  51. [59]

    The concave-convex procedure

    Alan L Yuille and Anand Rangarajan. The concave-convex procedure. Neural computation, 15 0 (4): 0 915--936, 2003

    2003

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.