Abstract
The decay of correlations (spatial mixing) property of spin systems plays an important role in approximate counting, Gibbs sampling, inference in graphical models, and studies of CSPs (constraint satisfaction problems). In this talk I will give a tutorial lecture on the decay of correlation in spin systems. The following topics will be discussed: (1) notions of spatial mixing; (2) how to establish decay of correlations with potential functions and other techniques; (3) how to establish decay of correlations on more general or more restrictive graph families; and (4) the possibilities for, and barriers to extending this scheme to general CSPs. Some implications of correlation decay in spin systems will also be explored, including: (1) fast convergence of the belief propagation algorithm, and (2) rapid mixing of Glauber dynamics.