We give a complete characterization of the two-state anti-ferromagnetic spin systems which are of strong spatial mixing on general graphs. We show that a two-state anti-ferromagnetic spin system is of strong spatial mixing on all graphs of maximum degree at most \Delta if and only if the system has a unique Gibbs measure on infinite regular trees of degree up to \Delta, where \Delta can be either bounded or unbounded. As a consequence, there exists an FPTAS for the partition function of a two-state antiferromagnetic spin system on graphs of maximum degree at most \Delta when the uniqueness condition is satisfied on infinite regular trees of degree up to \Delta. In particular, an FPTAS exists for arbitrary graphs if the uniqueness is satisfied on all infinite regular trees. This covers as special cases all previous algorithmic results for two-state anti-ferromagnetic systems on general-structure graphs.

Combining with the FPRAS for two-state ferromagnetic spin systems of Jerrum-Sinclair and Goldberg-Jerrum-Paterson, and the very recent hardness results of Sly-Sun,  this gives a complete classification, except at the phase transition boundary, of the approximability of all two-state spin systems, on either degree-bounded families of graphs or family of all graphs.

This is a joint work with Liang Li and Yitong Yin.

Bio: Dr. Pinyan Lu is a Lead Researcher at Theory Group of Microsoft Research Asia. He is also a Chair Professor at Shanghai Jiao Tong University. He studied in Tsinghua University (BS (2005) and PhD (2009) both in Computer Science). He is interested in theoretical computer science, including complexity theory, algorithms design and algorithmic game theory. Currently, his research is mainly focus on complexity and approximability of counting problems, and algorithmic mechanism design. He has received various awards, including the Best Paper Award in ICALP 2007, FAW 2010, ISAAC 2010 and so on. http://research.microsoft.com/en-us/people/pinyanl/