BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260922T122000Z
UID:Seminar-dept-1253@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20250204T130000
DTEND:20250204T140000
SUMMARY:School Seminar Series
DESCRIPTION:Andrei Krokhin: The complexity of Promise Constraint Satisfaction Problems\n\nThe constraint satisfaction problem (CSP) can be cast as the problem of deciding the existence of a homomorphism from one relational structure (e.g. a digraph) X to another structure A. By fixing the structure A, one obtains a large family of problems, denoted CSP(A). This family includes many well-known problems including k-satisfiability and graph k-colouring. The CSP dichotomy conjecture of Feder and Vardi, that was considered to be one of the important conjectures in theoretical computer science, stated that each CSP(A) is either polynomial-time solvable or NP-complete. Following a long sustained effort by a whole research community, the Feder-Vardi conjecture was confirmed in 2017 independently by Bulatov and Zhuk. The most remarkable thing about the theory behind the resolution of the conjecture is that it gives precise structural reasons for each CSP to have this or that complexity. In this talk, I will focus mainly on the Promise CSP (PCSP), a recent significant generalisation of the standard CSP, exemplified by the approximate graph colouring problem: given a 3-colourable graph, find (say) a 1000-colouring for it. I will describe the ongoing work towards building a similar theory for PCSPs, explain the key insights and mention some important open problems.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1253
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR