BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Cambridge Algorithms talks
SUMMARY:The complexity of finite-valued CSPs - Stanislav Z
ivny (University of Oxford)
DTSTART;TZID=Europe/London:20140609T100000
DTEND;TZID=Europe/London:20140609T110000
UID:TALK52894AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/52894
DESCRIPTION:Let L be a set of rational-valued functions on a f
ixed finite domain\; such a set is called a finite
-valued constraint language. We are interested in
the problem of minimising a function given explici
tly as a sum of functions from L. We establish a d
ichotomy theorem with respect to exact solvability
for all finite-valued languages defined on domain
s of arbitrary finite size. We present a simple al
gebraic condition that characterises the tractable
cases. Moreover\, we show that a single algorithm
based on linear programming solves all tractable
cases. Furthermore\, we show that there is a singl
e reason for intractability\; namely\, a very spec
ific reduction from Max-Cut.\n\n(based on work pub
lished at FOCS'12 and STOC'13\, joint work with J.
Thapper)
LOCATION:Computer Laboratory\, Room FW26
CONTACT:Dr Thomas Sauerwald
END:VEVENT
END:VCALENDAR