Spin Systems, Phase Transitions, Sampling and Approximation Algorithms

Add to your list(s) Download to your calendar using vCal

• Leslie Goldberg (University of Oxford)
• Wednesday 12 February 2014, 16:00-17:00
• Lecture Room C, Watson Building.

If you have a question about this talk, please contact José Cañizo.

This talk is part of the Mathematics Colloquium

A simple example of a spin system is the so-called hard-core model. This is actually a model of a gas, but it has a simple combinatorial interpretation. There is an underlying graph G, and “configurations’’ are just independent sets in G. The weight of a configuration is an (exponential) function of its size depending on a parameter lambda, and the “partition function’’ is the sum of the weights of all configurations. The Gibbs distribution (also called the Boltzmann distribution) is the distribution in which each configuration is sampled with probability proportional to its weight. It is useful to be able to sample from the Gibbs distribution and to calculate the value of the partition function, either exactly or approximately. The notion of Gibbs distribution extends to infinite graphs and a “phase transition’’ occurs when the parameter lambda is at a critical value such that, for smaller lambda there is unique Gibbs measure, whereas for larger lambda there are multiple Gibbs measures. Progress in recent years has shown that the computational complexity of the approximation problem on finite graphs is intimately connected with phase transitions, and with the question of uniqueness on infinite trees. I will give a survey of some of the results that are known, focussing especially on the special case where the Gibbs distribution is uniform.

This talk is part of the Analysis seminar series.

This talk is included in these lists:

• Analysis seminar
• Lecture Room C, Watson Building
• School of Mathematics events

Note that ex-directory lists are not shown.