1 citations · 1 across the 5 of their papers we have counts for
Showing 2026Show all
3 papers · 1 filter
cs.CC2026
When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
Timo Fritsch, Marvin Künnemann, Mirza Redzic +1
Consider the fundamental task of finding independent sets of (constant) size in a given -node hypergraph. How is the time complexity affected by the sparsity of the input, i…
cs.DS2026
Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
Bartłomiej Dudek, Nick Fischer, Geri Gokaj +4
We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schul…
cs.DS2026
Conditionally Tight Algorithms for Maximum k-Coverage and Partial k-Dominating Set via Arity-Reducing Hypercuts
Nick Fischer, Marvin Künnemann, Mirza Redzic
We revisit the classic Maximum -Coverage problem: Determine the largest number of elements that can be covered by choosing sets from a given family $\mathcal{F} = \{S_1,…