{"id":"f5156001-8214-4429-8907-3081cd98718c","arxiv_id":"2510.24550","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new hierarchy, t-sos submodularity, provides polynomial-time checkable sufficient conditions for submodularity and, at high t, an exact characterization.","lead":"This paper introduces a hierarchy of algebraic conditions called t-sum-of-squares submodularity that can certify whether a set function is submodular, each level checkable by a semidefinite program. It connects discrete optimization to real algebraic geometry and applies the new certificates to regression, submodularity ratio bounds, and difference-of-submodular optimization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Exactness at large t rests on an unstated external SOS bound, and Corollary 35 extends it to a non-hypercube variety without proof; this is the main unresolved support for the paper's central claim.","rationale":"The reader's conditional verdict is appropriate, and the weakest assumption identified is the same one I find most load-bearing: the exactness of the t-sos hierarchy at large t depends on an external sum-of-squares representation theorem that is not stated in the paper, together with an unproved extension in Corollary 35 to a non-hypercube variety. My reading of the manuscript found no clear internal contradiction in the main SDP construction or in the forward directions of the algebraic equivalences; the constructive proofs in Appendix A give real support to the framework, and the numerical experiments, though lacking error bars, are a reasonable first demonstration. The concern is therefore about missing and possibly nontrivial supporting material, not about a demonstrated falsehood. If the Sakaue bound is exactly as needed, Proposition 12 is correct; if not, the stated threshold is wrong. Corollary 35 is even less secure because the variety defined by I1[x,y] has three-point fibers and is not a Boolean hypercube, so the claimed exactness at t=ceil((n+d-1)/2) does not follow by a direct reduction to the cited theorem. This is enough to keep the verdict at CONDITIONAL: the paper's headline claims are plausible and well-motivated, but the proof of exactness is incomplete as written. I recommend no change to the reader's verdict, since the same concern that supports CONDITIONAL also stops short of demonstrating a fatal error.","tokens_in":40015,"tokens_out":32690,"duration_ms":284684,"concrete_test":"Brute-force/SDP test of Corollary 35 for n=5, d=4: generate a broad random sample of nonnegative monotone set functions with coefficients on a small grid, compute gamma* by exhaustive enumeration over all L,S in Definition 33, and compute gamma_t_sos by solving SDP (4) at t=ceil((n+d-1)/2)=4. If any instance yields gamma_t_sos < gamma*, the claimed exactness on I1[x,y] is false; if all instances match, the extension is numerically supported. As a secondary check, verify Proposition 12's bound on the degree-4 example of Proposition 27 at n=6, confirming that it is 3-sos-submodular but not 2-sos-submodular.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central exactness claim, Proposition 12, is load-bearing and is not established inside the paper: the 'if' direction is delegated to an unstated result from (Sakaue et al., 2016), whose precise hypothesis, degree bound, and applicability to the quotient by I2[x] cannot be verified from this manuscript. The threshold t=ceil((n+d-5)/2) has to match the Sakaue bound for polynomials of degree d-2 in n-2 variables; if the actual bound is instead ceil((n+d-4)/2) or worse, Proposition 12's stated threshold is wrong, even though a larger t might still yield exactness. More seriously, Corollary 35 extends the same representation claim to the variety of I1[x,y], i.e., {(x,y) in {0,1}^{2n} : x_i <= y_i}, asserting gamma* = gamma_t_sos at t=ceil((n+d-1)/2). This is not a Boolean hypercube: it is a product of three-point fibers (x_i,y_i) in {(0,0),(0,1),(1,1)}, and a naive reduction to a 2n-variable hypercube would give a much larger degree bound. The corollary is asserted without proof ('by using similar proof techniques'), so the equality for the submodularity-ratio application is unsupported. The same type of unsupported assertion appears in Section 4.3 ('It can further be shown that the decomposition ... is t-sos-submodular-irreducible') and in the uniqueness claim of Proposition 31. These are not merely exposition gaps: Proposition 12 and Corollary 35 are the statements that make the hierarchy exact and are reused in the applications.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":40318,"tokens_out":9177,"duration_ms":69965,"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":[{"comment":"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.","section":"Section 3.4, Appendix A.2, Proposition 12"},{"comment":"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].","section":"Section 4.2, Corollary 35"},{"comment":"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.","section":"Section 4.3, after equation (10)"}],"minor_comments":[{"comment":"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.","section":"Section 2.2, Proposition 3"},{"comment":"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.","section":"Section 3.4, Proposition 26"},{"comment":"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.","section":"Section 4.2, text near Figure 2"},{"comment":"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.","section":"Section 4.3, proofs of Propositions 39 and 41"},{"comment":"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.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the unverified external SOS bound underlying Proposition 12 and Corollary 35. I recommend asking the authors to either prove the needed representation bounds or state the theorem from (Sakaue et al., 2016) with full hypotheses and degree bound, and to verify whether the threshold in Proposition 12 is stated correctly. The paper would also benefit from moving the statement of the external theorem into the main text given its centrality."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take on 2510.24550. The paper introduces t-sos submodularity, a hierarchy of algebraic sufficient conditions for submodularity, checkable by SDP for fixed t. That is a genuinely new bridge between sos techniques and discrete optimization. The equivalent characterizations in Section 3.2, using the ideals I0 and I1, are non-obvious and the appendix proofs for those are largely complete. The SDP complexity table is useful and the choice of the second-order characterization is well justified.\n\nThe soft spot is exactness. Proposition 12 claims that for t = ceil((n+d-5)/2), t-sos submodularity coincides with submodularity for degree d. The proof delegates the crucial direction to an unstated result from Sakaue et al. 2016. I cannot verify from the manuscript that the stated threshold matches the external bound for polynomials of degree d-2 in n-2 variables; the arithmetic is delicate and may be off by a constant. More seriously, Corollary 35 extends the same sos representation claim to the variety {(x,y) : x_i <= y_i}, which is a product of three-point fibers, not a hypercube, and it does so with a hand-wave ('by using similar proof techniques'). That corollary is load-bearing for the submodularity-ratio application. Section 4.3 also asserts t-sos-irreducibility without proof. These are not cosmetic gaps; they are exactly the statements that make the hierarchy exact.\n\nThe numerical experiments are illustrative rather than conclusive: no error bars, no released code/data, and a few random instances. For a theory paper with application sections, that is acceptable if framed as a proof of concept, but the current text overstates the empirical case.\n\nOverall I think the core construction is sound and the paper deserves a serious referee. I would send it out with a request for major revision: either prove or precisely state the external sos bound, give a real argument for Corollary 35, and soften the unproven claims. If the threshold is off by one, that is probably fixable; if the I1 extension is genuinely harder, the applications need to be reworked. Either way, the central idea is worth engaging with.","headline":"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.","tokens_in":40893,"tokens_out":4478,"would_cite":true,"duration_ms":37885,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C27","13P10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["submodularity","sum of squares polynomials","semidefinite programming","set functions","multilinear extension","t-sos submodularity","submodular regression","submodularity ratio"],"falsifier":"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.","tokens_in":39764,"feed_emoji":"🧩","tokens_out":13517,"duration_ms":107340,"temperature":0.7,"pith_summary":"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.","feed_headline":"Sum-of-squares proof exists for every submodular function","feed_subtitle":"Each fixed level is a semidefinite check; at the top the hierarchy is exact, and it powers submodular regression.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the external theorem that nonnegative degree-$d$ polynomials on the Boolean cube are sos modulo the cube ideal with sos degree about $(n+d)/2$; Proposition 12 rests on this.","marker":"Sakaue et al., 2016"},{"why":"Establishes that testing submodularity of set functions of degree at least 4 is co-NP-complete, motivating a tractable sufficient hierarchy.","marker":"Crama, 1989"},{"why":"Shows submodularity is polynomial-time testable up to degree 3 and provides the cubic normal form used to prove all cubic submodular functions are 1-sos-submodular.","marker":"Billionnet and Minoux, 1985"},{"why":"Yields the lower bound on sos degree over the Boolean cube used to build the degree-4 example that is not $t$-sos for small $t$.","marker":"Laurent, 2003"},{"why":"Supplies sos-certificate degree bounds on the Boolean cube for nonnegative forms, used in Lemma 56 for the gap example.","marker":"Fawzi et al., 2015"},{"why":"Defines the submodularity ratio $\\gamma^*$ and the associated greedy approximation guarantee, the quantity bounded via SDP in Section 4.2.","marker":"Das and Kempe, 2018"},{"why":"Provides the approximation guarantee $(1-e^{-\\gamma^*})$ for greedy maximization of approximately submodular functions and the determinantal-function example used for numerical bounds.","marker":"Bian et al., 2017"}],"fun_headline_variants":["SOS hierarchy for submodularity, exact at top","Sum-of-squares certificates for submodular sets","SDP checkable submodularity via SOS","From diminishing returns to sum of squares","Tunable algebraic certificates for submodularity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["SOS hierarchy for submodularity, exact at top","Sum-of-squares certificates for submodular sets","SDP checkable submodularity via SOS","From diminishing returns to sum of squares","Tunable algebraic certificates for submodularity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000398,"raw_usage":{"total_tokens":2154,"prompt_tokens":1086,"completion_tokens":1068,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":702,"completion_tokens_details":{"reasoning_tokens":993}},"tokens_in":702,"tokens_out":1068,"duration_ms":8889,"temperature":1.0,"reasoning_tokens":993,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:41:15.562345+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Exact sdp relaxations with truncated moment matrix for binary polynomial optimization problems","cited_arxiv_id":null,"evidence_quote":"Supplies the external theorem that nonnegative degree-$d$ polynomials on the Boolean cube are sos modulo the cube ideal with sos degree about $(n+d)/2$; Proposition 12 rests on this."},{"cited_title":"Recognition problems for special classes of polynomials in 0--1 variables","cited_arxiv_id":null,"evidence_quote":"Establishes that testing submodularity of set functions of degree at least 4 is co-NP-complete, motivating a tractable sufficient hierarchy."},{"cited_title":"Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions","cited_arxiv_id":null,"evidence_quote":"Shows submodularity is polynomial-time testable up to degree 3 and provides the cubic normal form used to prove all cubic submodular functions are 1-sos-submodular."},{"cited_title":"Lower bound for the number of iterations in semidefinite hierarchies for the cut polytope","cited_arxiv_id":null,"evidence_quote":"Yields the lower bound on sos degree over the Boolean cube used to build the degree-4 example that is not $t$-sos for small $t$."},{"cited_title":"Sparse sum-of-squares certificates on finite abelian groups","cited_arxiv_id":null,"evidence_quote":"Supplies sos-certificate degree bounds on the Boolean cube for nonnegative forms, used in Lemma 56 for the gap example."},{"cited_title":"Guarantees for greedy maximization of non-submodular functions with applications","cited_arxiv_id":null,"evidence_quote":"Provides the approximation guarantee $(1-e^{-\\gamma^*})$ for greedy maximization of approximately submodular functions and the determinantal-function example used for numerical bounds."}],"review_version":2}