Spin Models: Connections Between Complexity, Phase Transition, Belief Propagation, and Induced Matrix Norms
Daniel Štefankovič ( University of Rochester )
- 16:00 23rd May 2014 ( week 4, Trinity Term 2014 )Room 051, Wolfson Building, Parks Road
What are the typical configurations of a spin model (for example, Ising model, or Potts model) on a random regular graph? We show that the answer to this question is characterised by tree recursions (belief propagation) and p->q operator matrix norms. Understanding the typical configurations allows us to show hardness of approximating the partition function for certain multispin models (for example, Potts model) on d-regular graphs in the non-uniqueness regime (that is, when the Gibbs measure on infinite d-regular tree is not unique). Joint work with Andreas Galainis and Eric Vigoda.