FG1 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.