DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.52

Testing k-Submodularity

Authors: Themistoklis Haris and Diptaksho Palit

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

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 𝓁_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.

Cite as

Themistoklis Haris and Diptaksho Palit. Testing k-Submodularity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 52:1-52:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{haris_et_al:LIPIcs.APPROX/RANDOM.2026.52,
  author =	{Haris, Themistoklis and Palit, Diptaksho},
  title =	{{Testing k-Submodularity}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{52:1--52:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.52},
  URN =		{urn:nbn:de:0030-drops-277694},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.52},
  annote =	{Keywords: property testing, sublinear algorithms, submodular functions}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.62

Relative-Error Unateness Testing

Authors: Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, and Yiding Zhang

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

The model of relative-error property testing of Boolean functions has been the subject of significant recent research effort [X. Chen et al., 2025; Chen et al., 2025; Chen et al., 2025]. In this paper we consider the problem of relative-error testing an unknown and arbitrary f: {0,1}ⁿ → {0,1} for the property of being a unate function, i.e. a function that is either monotone non-increasing or monotone non-decreasing in each of the n input variables. Our first result is a one-sided non-adaptive algorithm for this problem that makes Õ(log(N)/ε) samples and queries, where N = |f^{-1}(1)| is the number of satisfying assignments of the function that is being tested and the value of N is given as an input parameter to the algorithm. Building on this algorithm, we next give a one-sided adaptive algorithm for this problem that does not need to be given the value of N and with high probability makes Õ(log(N)/ε) samples and queries. We also give lower bounds for both adaptive and non-adaptive two-sided algorithms that are given the value of N up to a constant multiplicative factor. In the non-adaptive case, our lower bounds essentially match the complexity of the algorithm that we provide.

Cite as

Xi Chen, Diptaksho Palit, Kabir Peshawaria, William Pires, Rocco A. Servedio, and Yiding Zhang. Relative-Error Unateness Testing. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ICALP.2026.62,
  author =	{Chen, Xi and Palit, Diptaksho and Peshawaria, Kabir and Pires, William and Servedio, Rocco A. and Zhang, Yiding},
  title =	{{Relative-Error Unateness Testing}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.62},
  URN =		{urn:nbn:de:0030-drops-264511},
  doi =		{10.4230/LIPIcs.ICALP.2026.62},
  annote =	{Keywords: Property Testing, Relative Error}
}

Search Results

Documents authored by Palit, Diptaksho

Testing k-Submodularity

Abstract

Cite as

Relative-Error Unateness Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message