BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Theoretical computer science seminar
SUMMARY:Why promises matter in constraint satisfaction? -
Jakub OprÅ¡al (University of Birmingham)
DTSTART:20231006T100000Z
DTEND:20231006T105000Z
UID:TALK5350AT
URL:/talk/index/5350
DESCRIPTION:*Zoom details*\n\n* Link: https://bham-ac-uk.zoom.
us/j/81873335084?pwd=T1NaUFg2U1l6d0RLL2RlTzFBam1IU
T09\n* Meeting ID: 818 7333 5084\n* Passcode: 217\
n\n*Abstract*\n\nDichotomy conjecture of Feder and
Vardi (1998)\, which claims that every fixed-temp
late constraint satisfaction problem (CSP) with a
finite domain is either NP-complete or solvable in
polynomial time\, was a main driving force in the
research of computational complexity of CSPs unti
l its resolution in 2017. Since the resolution of
the CSP dichotomy\, a promise version of the probl
em called *promise CSP* is gaining a lot of tracti
on.\n\nAmong other problems\, this framework can e
xpress the problem of colouring of a 3-colourable
graph that with $k$ colours for a fixed k > 3 (the
fact that the graph is 3-colourable is given as a
*promise*\, hence the problem is non-trivial). We
can ask under which conditions on $k$ does this p
roblem become tractable? While this question has b
een around since 70's\, and many people agree on w
hat the answer should be\, there is surprisingly l
ittle known to this day.\n\nUnlike the universally
-algebraic methods that were used to address the a
bove-mentioned CSP dichotomy\, many different appr
oaches (including\, e.g.\, algebraic topology) are
used in the scope of promise CSPs. This makes the
field more open to insights from other directions
. I will give a brief overview of the current stat
e-of-matters in promise CSPs\, and outline a few r
easons why I believe that now is a great time to j
oin.
LOCATION:LG23\, Computer Science // Zoom
CONTACT:George Kaye
END:VEVENT
END:VCALENDAR