Title: The algebraic method for Constraint Satisfaction Problems

Abstract: Constraint satisfaction problems (CSPs) encompass a very broad range of computational problems in both application and theory.  The case of fixed template CSPs corresponds exactly to homomorphism problems for fixed relational structures, and include all of the main SAT variants such as 3SAT, not-all-equal-3SAT, HornSAT, as well as combinatorial problems such as graph 3-colourability, directed graph unreachability, and algebraic problems such as solvability of linear equations over finite fields.  In the 1990s, Feder and Vardi conjectured a broadest logically definable subclass of NP in which a dichotomy might hold: all problems are either NP-complete or solvable in polynomial time. They showed that this class was equivalent to the class of fixed template CSPs.  The Feder-Vardi Dichotomy Conjecture was solved positively in 2017, independently by Bulatov and Zhuk.

This talk will survey the so-called "algebraic method" for analyzing the complexity of fixed template CSPs, which underlies the basic approach taken by both Bulatov and Zhuk.  Also discussed will be the role of the algebraic method in finer complexity theoretic analysis of CSPs, and of related computational problems, such as detecting implied constraints.