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.
Blogger's Review: This paper innovatively explores the testing of $k$-submodular functions, highlighting significant differences from classical submodular functions. By combining theory with practical testing methods, the authors provide new insights that are particularly valuable in the application scenarios of multidimensional data structures.