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\, Departmen
 t of Computer Science University of Oxford
DTSTART:20140609T090000Z
DTEND:20140609T100000Z
UID:TALK52947@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 characte
 rises the tractable cases. Moreover\, we show that a single algorithm base
 d on linear programming solves all tractable cases.\nFurthermore\, we show
  that there is a single reason for intractability\; namely\, a very specif
 ic reduction from Max-Cut.\n\n
LOCATION:FW26\, Computer Laboratory\, William Gates Builiding
END:VEVENT
END:VCALENDAR