A Complexity Dichotomy for Partition Functions with Mixed Signs

Leslie Ann Goldberg, Martin Grohe, Mark Jerrum & Marc Thurley
\emph{Partition functions}, also known as \emph{homomorphism functions}, form a rich family of graph invariants that contain combinatorial invariants such as the number of $k$-colourings or the number of independent sets of a graph and also the partition functions of certain ``spin glass'' models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill (2000) and Bulatov and Grohe (2005), we completely classify the computational complexity of partition functions. Our...