18 citations · 34 across the 4 of their papers we have counts for
6 papers
Polynomial-time Tests for Difference Terms in Idempotent Varieties
William DeMeo, Ralph Freese, Matthew Valeriote
We consider the following practical question: given a finite algebra A in a finite language, can we efficiently decide whether the variety generated by A has a difference term? We…
Sensitive instances of the Constraint Satisfaction Problem
Libor Barto, Marcin Kozik, Johnson Tan +1
We investigate the impact of modifying the constraining relations of a Constraint Satisfaction Problem (CSP) instance, with a fixed template, on the set of solutions of the instanc…
Deciding the existence of minority terms
Alexandr Kazda, Jakub Opršal, Matt Valeriote +1
This paper investigates the computational complexity of deciding if a given finite idempotent algebra has a ternary term operation that satisfies the minority equations $m(y,x,…
Deciding some Maltsev conditions in finite idempotent algebras
Alexandr Kazda, Matt Valeriote
In this paper we investigate the computational complexity of deciding if a given finite algebraic structure satisfies a fixed (strong) Maltsev condition . Our goal in this paper…
Generic Expression Hardness Results for Primitive Positive Formula Comparison
Simone Bova, Hubie Chen, Matthew Valeriote
We study the expression complexity of two basic problems involving the comparison of primitive positive formulas: equivalence and containment. In particular, we study the complexit…
On tractability and congruence distributivity
Emil Kiss, Matthew Valeriote
Constraint languages that arise from finite algebras have recently been the object of study, especially in connection with the Dichotomy Conjecture of Feder and Vardi. An important…