Informatics Colloquium 6. 11. Power of algorithms for homomorphisms and generalisations seen . . .
Informatics Colloquium 6. 11. 2018, 14:00 lecture hall D2
Assoc. Prof. Dr. Standa Živný, Department of Computer Science, University of
Oxford
Power of algorithms for homomorphisms and generalisations seen from both sides
Abstract: The topic of this talk is the computational complexity of and the
power of algorithms for the homomorphism problem between two relational
structures, also known as the constraint satisfaction problem (CSP). We briefly
discuss the known algorithmic and complexity classifications for CSPs
parametrised by the source or target structures.
We then discuss in more detail a classification of general-valued CSPs
parametrised by the source structures. This part of the talk is based on joint
work (published in FOCS 2018) with Clement Carbonnel and Miguel Romero.