Testing k-submodularity

Themistoklis Haris, Diptaksho Palit

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 $…