Abstract
In this talk, we will present the basic results of the theory of the algebraic approach to CSP, formulated by Bulatov, Jeavons and Krokhin in 2005. This approach was a fundamental building block in solving the so-called Feder-Vardi conjecture (1988), which Zhukov and Bulatov managed to solve independently in 2017. We will also focus on a generalization of CSP, the so-called Promise CSP, where we can assume certain additional properties for the input instance. Although the theory of the algebraic approach to CSP in its essence does not make sense for PCSP, its main aspects have been successfully transferred to the world of PCSP.
The main goal of the lecture is to outline the basic results of the algebraic approach to PCSP. We will use the language of category theory, with the help of which we will see that these results are not specific in any way, but on the contrary, are based on well-known and proven techniques. For example, we will rely on the Grothendieck construction, which has its origins in algebraic topology.
By formalizing the original results using the language of category theory, our theorems hold in a more general way. As a result, we get that the basic results of the algebraic approach to PCSP also hold for finite-dimensional simplicial sets or multi-sort structures.