A Complexity Dichotomy for Hypergraph Partition Functions

Prof. Leslie Goldberg (University of Liverpool)

Info

Date	13th March 2009 (week 8, Hilary Term 2009)
Time	14:00
Place	Lecture Theater B

Abstract

The talk will introduce "partition functions", which arise in many computational contexts, and will discuss the complexity of computing them. It will explain what a "dichotomy theorem" is, and why we want such theorems (essentially, we want them so that we can better understand the boundary between the class of easy-to-compute functions and the class of functions that cannot be efficiently computed).

The particular technical problem which forms the foundation for the talk is the complexity of counting homomorphisms from an r-uniform hypergraph G to a symmetric r-ary relation H. (But you don't need to know anything about that to understand the talk!) We give a dichotomy theorem for r > 2, showing for which H this problem is in FP and for which H it is #P-complete. Our dichotomy theorem extends to the case in which the relation H is weighted, and the partition function to be computed is the sum of the weights of the homomorphisms. This problem is motivated by statistical physics, where it arises as computing the partition function for particle models in which certain combinations of r sites interact symmetrically.

This is joint work with Martin Dyer and Mark Jerrum.