5 citations · 5 across the 1 of their papers we have counts for
3 papers
cs.LO2020
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…
cs.CC2019★ 5 cited
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…
math.GR2018
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.…