{"ID":5346700,"CreatedAt":"2026-06-30T04:09:55.830587294Z","UpdatedAt":"2026-07-02T15:01:14.507804213Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.30433","arxiv_id":"2606.30433","title":"Testing k-submodularity","abstract":"We initiate the study of property testing for $k$-submodular functions, a higher-dimensional analogue of submodular functions defined on partial partitions of a ground set. While $k$-submodularity retains the diminishing-returns flavor of ordinary submodularity, it also introduces a pairwise monotonicity constraint comparing competing assignments of the same element. This additional local structure makes the testing problem qualitatively different from the classical case. Our results show a sharp contrast between distance regimes. In the $\\ell_p$ regime for $p \\geq 1$, we prove that every bounded $k$-submodular function is close to a junta on the hypergrid. Combined with an implicit-learning tester for hypergrid domains, this yields a constant-query tester for $k$-submodularity. In the Hamming distance regime, $k$-submodularity admits two qualitatively different local witnesses -- violated squares for diminishing marginal gains, and violated triangles for pairwise-monotonicity failures -- and the latter has no counterpart at $k=1$. We prove density theorems for both witness types via repair on filters and ideals of partial partitions, yielding non-adaptive, one-sided sub-exponential-query testers for the two component properties of $k$-submodularity. We then exhibit a configuration in which the two repair directions are forced into opposition on a shared vertex, identifying a structural barrier to combining these into a tester for the full property. Finally, for bounded-range functions, we give an adaptive tester for monotone $k$-submodularity via a pseudo-DNF representation and learning on the hypergrid. Several of the structural and learning tools developed here may be useful for testing other properties over product domains.","short_abstract":"We initiate the study of property testing for $k$-submodular functions, a higher-dimensional analogue of submodular functions defined on partial partitions of a ground set. While $k$-submodularity retains the diminishing-returns flavor of ordinary submodularity, it also introduces a pairwise monotonicity constraint com...","url_abs":"https://arxiv.org/abs/2606.30433","url_pdf":"https://arxiv.org/pdf/2606.30433v1","authors":"[\"Themistoklis Haris\",\"Diptaksho Palit\"]","published":"2026-06-29T15:11:18Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}