Algebra Seminar talk
2017-11-24
Libor Barto (Univerzita Karlova)
Promise Constraint Satisfaction Problem
Abstract:
Fixed-template Promise Constraint Satisfaction Problem (PCSP) is a
framework which enables to express problems such as finding a 579-coloring of a
3-colorable graph. I will talk about universal algebraic approach to PCSPs and
selected algorithmic/hardness results.