The expressive power of binary submodular functions

Standa Zivny

In this talk we study the problem of whether all submodular polynomials can be
expressed as projections of quadratic submodular polynomials over a larger set
of variables. It has been known that this is true for cubic submodular
polynomials, and conjectured true for all submodular polynomials. We show a new
class of submodular polynomials of arbitrary arities which can indeed be
expressed in this way. More importantly, we show that in general this is not the
case, thus refuting a long-standing open problem. We show the connection between
the expressibility of submodular functions by binary submodular functions and
the minimisation of submodular functions via min-cuts.

These problems play an important role in pseudo-Boolean optimisation, artificial
intelligence, where they are known as soft, weighted or valued constraint
satisfaction problems, and in computer vision, where there are known as Gibbs
energy minimisation or MAP inference in Markov Random Fields.

Some preliminary parts of this work were presented at CP'08 and INFORMS'08. The
talk will also include newer results which have not been published yet.