Jakub Opršal – Promises, constraints, and problems: Beyond universal algebra
Durham University
The promise constraints satisfaction problem (PCSP) is a class of computational problems that can be seen as a certain structural approximation version of the CSP. It can express the problem of finding 6-colouring of a graph that is promised to be 3-colourable, and similar more general problems.
In the first part, we will present the basic 'algebraic' theory of promise constraint satisfaction, and provide the background necessary to approach the problems.
In the second part, we will talk about recent tools used in PCSPs that go beyond the algebraic approach, and provide a list of selected open problems and possible research directions.