Showing cs.DSShow all
2 papers · 1 filter
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.DS2025
Engineering Dominating Patterns: A Fine-grained Case Study
Jonathan Dransfeld, Marvin Künnemann, Mirza Redzic +1
The \emph{Dominating -Pattern} problem generalizes the classical -Dominating Set problem: for a fixed \emph{pattern} and a given graph , the goal is to find an induced…