Skip to main content

Spin Models: Connections Between Complexity, Phase Transition, Belief Propagation, and Induced Matrix Norms

Daniel Štefankovič ( University of Rochester )

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.

Speaker bio

Daniel Štefankovič is an Associate Professor in the Department of Computer Science at University of Rochester. He received a PhD from the University of Chicago in 2005 and a BS from Comenius University in 1998. His research interests include graph drawing, counting and sampling, coding theory, mathematical modeling in biology, and learning theory.

 

 

Share this: