LFCS semianr by Stanislav Zivny: The complexity of finitevalued CSPs
The complexity of finitevalued CSPs Stanislav Zivny (Oxford) (based on work published at FOCS'12 and STOC'13, joint work with J. Thapper)
What 


When 
Feb 25, 2014 from 04:00 PM to 05:00 PM 
Where  IF 4.314.33 
Contact Name  Ilias Diakonikolas 
Add event to calendar 
vCal iCal 
Abstract:
Let L be a set of rationalvalued functions on a fixed finite domain; such a set is called a finitevalued constraint language. We are interested in the problem of minimising a function given explicitly as a sum of functions from L. We establish a dichotomy theorem with respect to exact solvability for all finitevalued languages defined on domains of arbitrary finite size. We present a simple algebraic 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 single reason for intractability; namely, a very specific reduction from MaxCut.