17 citations · 46 across the 14 of their papers we have counts for
15 papers
The subpower membership problem of 2-nilpotent algebras
Michael Kompatscher
The subpower membership problem SMP(A) of a finite algebraic structure A asks whether a given partial function from A^k to A can be interpolated by a term operation of A, or not. W…
Polynomial definability in constraint languages with few subpowers
Jakub Bulín, Michael Kompatscher
A first-order formula is called primitive positive (pp) if it only admits the use of existential quantifiers and conjunction. Pp-formulas are a central concept in (fixed-template)…
The local-global property for G-invariant terms
Alexandr Kazda, Michael Kompatscher
For some Maltsev conditions it is enough to check if a finite algebra satisfies locally on subsets of bounded size, in order to decide, whether sati…
CSAT and CEQV for nilpotent Maltsev algebras of Fitting length > 2
Michael Kompatscher
The circuit satisfaction problem CSAT(A) of an algebra A is the problem of deciding whether an equation over A (encoded by two circuits) has a solution or not. While solving system…
When symmetries are not enough: a hierarchy of hard Constraint Satisfaction Problems
Pierre Gillibert, Julius Jonušas, Michael Kompatscher +2
We produce a class of -categorical structures with finite signature by applying a model-theoretic construction -- a refinement of the Hrushosvki-encoding -- to -categorical s…
CC-circuits and the expressive power of nilpotent algebras
Michael Kompatscher
We show that CC-circuits of bounded depth have the same expressive power as circuits over finite nilpotent algebras from congruence modular varieties. We use this result to phrase…