2026-09-10T09:44:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27769 2026-09-09T12:19:37Z ddc:004 open_access

Testing k-Submodularity Haris, Themistoklis Palit, Diptaksho property testing sublinear algorithms submodular functions 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 𝓁_p regime for p ≥ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Themistoklis Haris and Diptaksho Palit 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.52 urn:nbn:de:0030-drops-277694 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.52 eng https://creativecommons.org/licenses/by/4.0/legalcode