Xiaoyang Gong: Maltsev Constraints are tractable

Abstract

One of the most sighificant achievements in the study of Constraint Satisfaction Problems (CSPs) is a result due to Bulatov [ECCC 2002], which establishes that every constraint language $\Gamma$ – a set of relations over a finite domain-that is invariant under a Mal’tsev operation, i.e.,a ternary operation $p$ satisfying

$$p(x, y, y) = p(y, y, x) = x \quad \text{for all } x, y,$$

gives rise to a tractable problem class. This result both subsumes and generalizes several previously known tractable fragments of the CSP, including affine constraint problems [JACM 1997, STOC 1978] and constraint satisfaction problems over finite groups with near-subgroups and their cosets [SIAM J. Computing 1998]. Moreover, it has become a cornerstone of more recent developments in the field, most notably the complete complexity classification of CSPs over three-element domains [FOCS 2002] and the resolution of the conservative CSP [LICS 2003].
This talk presents the simplified proof of tractability for CSPs admitting a Mal’tsev polymorphism, following the treatment of Bulatov and Dalmau [SIAM J. Computing 2006).