An instance of the Constraint Satisfaction Problem (CSP) is given by a set of constraints over a set of variables. The variables take values from a (finite) domain and the constraints are specified by relations over the domain that need to hold between various subsets of variables. In the late 90s, it was realised that the complexity of the CSP restricted to some fixed set of relations is captured by an associated set of operations called polymorphisms. This connection has lead to a great influx of ideas and tools (as well as researchers) from universal algebra, a field of mathematics that in particular studies algebras of such operations.

A quite general optimisation version of the CSP is obtained by replacing the relations by arbitrary functions from tuples of domain values to the rationals extended with positive infinity. The goal of this problem, called the Valued Constraint Satisfaction Problem (VCSP), is to minimise a sum of such functions over all assignments. The complexity classification project of the VCSP has taken some great strides over the last four years and has recently been reduced to its more famous decision problem counterpart: the dichotomy conjecture for the CSP.

I will talk about how polymorphisms appear in the study of the CSP and some of what universal algebra has taught us. I will then show how these results can be used for characterising the efficacy of Sherali-Adams linear programming relaxations of the VCSP.

This is based on joint work with Standa Zivny, University of Oxford (UK).