Stanislav Zivny, University of Oxford; Micrsoft Research Lectures

Add to your list(s) Download to your calendar using vCal

• Stanislav Zivny - University of Oxford
• Monday 12 April 2010, 14:00-15:00
• Small public lecture room, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

This talk has been canceled/deleted

Abstract: In this talk, I will present the concept of submdodularity and relate it to certain optimisation problems, which can be described as Valued Constraint Satisfaction Problems. This framework is equivalent to other frameworks, for instance, pseudo-Boolean polynomials, Gibbs energy minimisation or Markov Random Fields. It has previously been an open problem whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This problem has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. We answer the problem negatively. We relate our results to the problem of which submodular functions can be minimised using the Min-Cut/Max-Flow techniques.

This talk is part of the Microsoft Research Cambridge, public talks series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.