Homomorphisms and generalisations seen from both sides

Decanato - Facoltà di scienze informatiche

Data: 14 Marzo 2018 / 11:30 - 12:30

USI Lugano Campus, room A23, Red building (Via G. Buffi 13)

Speaker:	Standa Zivny
	Univeristy of Oxford, UK
Date:	Wednesday, March 14, 2018
Place:	USI Lugano Campus, room A23, Red building (Via G. Buffi 13)
Time:	11:30-12:30

Abstract:

The topic of this talk is the computational complexity of the homomorphism problem between two relational structures, also known as the constraint satisfaction problem (CSP). We briefly discuss the known classifications of CSPs parametrised by the source or target structures. We then discuss a classification of general-valued CSPs parametrised by the source structures.
Based on joint work with Clement Carbonnel and Miguel Romero.

Biography:

I grew up in Sobeslav, a small town in the south of Bohemia, Czech republic. Before coming to England, I read computer science in the Czech republic, Netherlands, and Finland. I came to Oxford in 2006 and spent here three years as a doctoral student working on my thesis that won the ACP doctoral research award and was then published by Springer as a monograph and three years as a stipendiary Junior Research Fellow in Mathematical and Physical Sciences at Oxford's University College. After a year at Warwick, I came back to Oxford in 2013.
Research interests: algorithms, computational complexity, constraint satisfaction, discrete optimization.

Host:

Prof. Monaldo Mastrolilli