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…
Circuit equivalence in 2-nilpotent algebras
Piotr Kawałek, Michael Kompatscher, Jacek Krzaczkowski
The circuit equivalence problem of a finite algebra is the computational problem of deciding whether two circuits over define the same function or not. This…
Some notes on extended equation solvability and identity checking for groups
Michael Kompatscher
Every finite non-nilpotent group can be extended by a term operation such that solving equations in the resulting algebra is NP-complete and checking identities is co-NP-complete.…
Forbidden cycles in metrically homogeneous graphs
Jan Hubička, Michael Kompatscher, Matěj Konečný
In a recent paper by a superset of the authors it was proved that for every primitive 3-constrained space of finite diameter from Cherlin's catalogue of metrically homogene…
The equation solvability problem over nilpotent Mal'cev algebras
Michael Kompatscher
By a result of Horváth the equation solvability problem over finite nilpotent groups and rings is in P. We generalize his result, showing that the equation solvability over every f…
Ramsey expansions of metrically homogeneous graphs
Andrés Aranda, David Bradley-Williams, Jan Hubička +4
We investigate Ramsey expansions, the coherent extension property for partial isometries (EPPA), and the existence of a stationary independence relation for all classes of metrical…
Equations in oligomorphic clones and the Constraint Satisfaction Problem for -categorical structures
Libor Barto, Michael Kompatscher, Miroslav Olšák +2
There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of…
A complexity dichotomy for poset constraint satisfaction
Michael Kompatscher, Trung Van Pham
In this paper we determine the complexity of a broad class of problems that extends the temporal constraint satisfaction problems. To be more precise we study the problems Poset-SA…
A counterexample to the reconstruction of -categorical structures from their endomorphism monoids
Manuel Bodirsky, David Evans, Michael Kompatscher +1
We present an example of two countable -categorical structures, one of which has a finite relational language, whose endomorphism monoids are isomorphic as abstract monoids, but…
pairwise non-isomorphic maximal-closed subgroups of Sym via the classification of the reducts of the Henson digraphs
Lovkush Agarwal, Michael Kompatscher
Given two structures and on the same domain, we say that is a reduct of if all -definable relations of $\mathcal{…