Ross Willard, Department of Pure Mathematics, University of Waterloo
“Congruence meet semi-distributive varieties”
Feder and Vardi conjectured that a fixed-template constraint satisfaction problem CSP(D) is solvable by local consistency methods if and only if it cannot simulate linear equations over any finite field. In this lecture I will describe the known characterizations of templates D with the property that CSP(D) fails to simulate linear equations; all characterizations refer to the polymorphism algebra of D and the variety that this algebra generates. It turns out that CSP(D) fails to simulate linear equations if and only if the variety generated by the polymorphism algebra is congruence meet semi-distributive; equivalently, if the variety has no abelian congruences. This lecture is preparation for lectures in the winter 2014 term in which the recent solution of the Feder-Vardi conjecture, due to Barto and Kozik, will be presented.