Speaker:
Daniel Stefankovic
Title:
Spin models: connections between complexity, phase transition,
belief propagation, and induced matrix norms
Abstract:
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.