Speaker
Jakub Opršal, ISTA
Title
An invitation to Promise Constraint Satisfaction Problem
Abstract
Dichotomy conjecture of Feder and Vardi [1998], which claims that every fixed-template constraint satisfaction problem (CSP) with a finite domain is either NP-complete or solvable in polynomial time, was a main driving force in the research of computational complexity of CSPs until its resolution in 2017. This research was focused on a development and application of universal algebra.
A recent direction, which is focused on a promise version of the problem called *promise CSP*, is gaining a lot of traction since the resolution of the CSP dichotomy. The key difference from the standard CSP is that universal-algebraic tools are not enough to prove hardness, and many different approaches (including, e.g., algebraic topology) are used instead. This makes the field less reliant on deep knowledge of universal algebra and more open to insights from other directions.
Slides
An invitation to Promise Constraint Satisfaction Problem
