Speaker: Daniel Stefankovic

Title: Spin models: connections between complexity, phase transition, belief propagation, and induced matrix norms


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 characterized 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 Galanis, and Eric Vigoda.