BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The complexity of finite-valued CSPs - Stanislav Zivny (University
  of Oxford)
DTSTART:20140609T090000Z
DTEND:20140609T100000Z
UID:TALK52894@talks.cam.ac.uk
CONTACT:Dr Thomas Sauerwald
DESCRIPTION:Let L be a set of rational-valued functions on a fixed finite 
 domain\; such a set is called a finite-valued constraint language. We are 
 interested in the problem of minimising a function given explicitly as a s
 um of functions from L. We establish a dichotomy theorem with respect to e
 xact solvability for all finite-valued languages defined on domains of arb
 itrary finite size. We present a simple algebraic condition that character
 ises the tractable cases. Moreover\, we show that a single algorithm based
  on linear programming solves all tractable cases. Furthermore\, we show t
 hat there is a single reason for intractability\; namely\, a very specific
  reduction from Max-Cut.\n\n(based on work published at FOCS'12 and STOC'1
 3\, joint work with J.Thapper)
LOCATION:Computer Laboratory\, Room FW26
END:VEVENT
END:VCALENDAR