News and events archive
From the faculty
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.