Statistical Mechanics of Unsatisfiability and Glasses

Region-graph belief-propagation and survey propagation for lattice spin-glass models

26 May 2012, 10:15

45m

Ferry Stockholm-Mariehamn and Hotel Arkipelag, Mariehamn, Åland

Synthesis

Speaker

Prof. Haijun Zhou (Institute of Theoretical Physics, the Chinese Academy of Sciences, Beijing, China)

Description

Graphical models for finite-dimensional spin glasses and real-world combinatorial optimization and satisfaction problems usually have an abundant number of short loops. The cluster variation method and its extension, the region graph method, are theoretical approaches for treating the complicated short-loop-induced local correlations. For graphical models represented by non-redundant or redundant region graphs, we construct approximate free energy landscapes through the mathematical framework of region graph partition function expansion. During this construction, we are able to derive the region graph belief- propagation equation and the region-graph survey propagation equation as conditions to ensure vanishing free-energy correction contributions from region subgraphs with dangling edges.

As a simple application of the general theory, we perform region graph belief-propagation simulations on the square- lattice ferromagnetic Ising model and the Edwards- Anderson model. Collective domains of different sizes in the disordered and frustrated square lattice are identified by the message-passing procedure. Such collective domains and the frustrations among them are responsible for the low- temperature glass like dynamical behaviors of the system.

J.-Q. Xiao, Haijun Zhou, "Partition function loop series for a general graphical model: free energy corrections and message passing equations", Journal of Physics A: Mathematical and Theoretical 44, 425001 (2011).

Haijun Zhou, Chuang Wang, Jing-Qing Xiao, Zedong Bi, "Partition function expansion on region-graphs and message-passing equations", Journal of Statistical Mechanics: Theory and Experiment, L12001 (2011).

Haijun Zhou, Chuang Wang, "Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results", submitted to Journal of Statistical Physics (2012), [arXiv:1204.1818].