BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Submodularity and Valued Constraint Satisfaction Problems - Stanis
 lav Zivny - University of Oxford
DTSTART:20100412T130000Z
DTEND:20100412T140000Z
UID:TALK23996@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:*Abstract:* In this talk\, I will present the concept of submd
 odularity and relate it to certain optimisation problems\, which can be de
 scribed as Valued Constraint Satisfaction Problems. This framework is equi
 valent to other frameworks\, for instance\, pseudo-Boolean polynomials\, G
 ibbs energy minimisation or Markov Random Fields. It has previously been a
 n open problem whether all Boolean submodular functions can be decomposed 
 into a sum of binary submodular functions over a possibly larger set of va
 riables. This problem has been considered within several different context
 s in computer science\, including computer vision\, artificial intelligenc
 e\, and pseudo-Boolean optimisation. We answer the problem negatively. We 
 relate our results to the problem of which submodular functions can be min
 imised using the Min-Cut/Max-Flow techniques. 
LOCATION:Small public lecture room\, Microsoft Research Ltd\, 7 J J Thomso
 n Avenue (Off Madingley Road)\, Cambridge
END:VEVENT
END:VCALENDAR