Title: An investigation of the complexity of approximating weighted Boolean counting CSPs

Speaker: Mark Jerrum

Classical constraint satisfaction problems (CSPs) model generalised
satisfiability problems.  Originally, it was the decision version (is there
a satisfying assignment?) that was studied, but the counting version (how
many assignments?) has recently attracted attention. By replacing relational
constraints by functional ones, one can extend the model the cover weighted
counting problems of the sort encountered in statistical physics.  In this
talk I will describe some recent work in which we begin to study the
complexity of approximating CSPs of this kind. ``Log-supermodular''
functions play a role in the complexity classification.

This is joint work by Andrei Bulatov, Martin Dyer, Leslie Goldberg and Mark Jerrum