Search Results

Documents authored by Haris, Themistoklis


Document
RANDOM
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
Counting Simplices in Hypergraph Streams

Authors: Amit Chakrabarti and Themistoklis Haris

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied problem of estimating the number of triangles in a graph stream. Our input is a k-uniform hypergraph H with n vertices and m hyperedges, each hyperedge being a k-sized subset of vertices. A k-simplex in H is a subhypergraph on k+1 vertices X such that all k+1 possible hyperedges among X exist in H. The goal is to process the hyperedges of H, which arrive in an arbitrary order as a data stream, and compute a good estimate of T_k(H), the number of k-simplices in H. We design a suite of algorithms for this problem. As with triangle-counting in graphs (which is the special case k = 2), sublinear space is achievable but only under a promise of the form T_k(H) ≥ T. Under such a promise, our algorithms use at most four passes and together imply a space bound of O(ε^{-2} log δ^{-1} polylog n ⋅ min{(m^{1+1/k})/T, m/(T^{2/(k+1)})}) for each fixed k ≥ 3, in order to guarantee an estimate within (1±ε)T_k(H) with probability ≥ 1-δ. We also give a simpler 1-pass algorithm that achieves O(ε^{-2} log δ^{-1} log n⋅ (m/T) (Δ_E + Δ_V^{1-1/k})) space, where Δ_E (respectively, Δ_V) denotes the maximum number of k-simplices that share a hyperedge (respectively, a vertex), which generalizes a previous result for the k = 2 case. We complement these algorithmic results with space lower bounds of the form Ω(ε^{-2}), Ω(m^{1+1/k}/T), Ω(m/T^{1-1/k}) and Ω(mΔ_V^{1/k}/T) for multi-pass algorithms and Ω(mΔ_E/T) for 1-pass algorithms, which show that some of the dependencies on parameters in our upper bounds are nearly tight. Our techniques extend and generalize several different ideas previously developed for triangle counting in graphs, using appropriate innovations to handle the more complicated combinatorics of hypergraphs.

Cite as

Amit Chakrabarti and Themistoklis Haris. Counting Simplices in Hypergraph Streams. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chakrabarti_et_al:LIPIcs.ESA.2022.32,
  author =	{Chakrabarti, Amit and Haris, Themistoklis},
  title =	{{Counting Simplices in Hypergraph Streams}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{32:1--32:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.32},
  URN =		{urn:nbn:de:0030-drops-169705},
  doi =		{10.4230/LIPIcs.ESA.2022.32},
  annote =	{Keywords: data streaming, graph algorithms, hypergraphs, sub-linear algorithms, triangle counting}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail