Fri 12 Dec at 10:15
Mikko Koivisto
The Magnificent Potts Model: A Computational Perspective
Abstract:
The Potts model is a popular probabilistic model of complex´systems governed by nearest neighbor interactions. Its behavior
is encoded in the so-called partition function of the model. The Potts partition function can be viewed as a special case of
the Tutte polynomial that captures a host of fundamental graph invariants, such as the chromatic, flow and reliability polynomials.
We review the computational complexity of evaluating the Potts partition function and the Tutte polynomial. Specifically, we show
how the Tutte polynomial of any n-vertex graph can be computed in time 2^n poly(n), or in time 3^n poly(n) and space poly(n), via
evaluations of the Potts partition function.
Based on joint work with A. Björklund, T. Husfeldt, and P. Kaski:
Computing the Tutte polynomial in vertex-exponential time. FOCS 2008.
Last updated on 12 Dec 2008 by Visa Noronen - Page created on 12 Dec 2008 by Visa Noronen