MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Correlation Decay up to Uniqueness in Spin Systems

Pinyan Lu
Microsoft Research Asia; Shanghai Jiao Tong University
Talk

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 mainly interested in complexity theory, algorithms design and algorithmic game theory. 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/
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Friday, 2 November 2012
13:00
60 Minutes
E1 4
024
Saarbrücken

Abstract

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.

Contact

Mengji Xia
--email hidden
passcode not visible
logged in users only

Mengji Xia, 10/29/2012 12:58
Mengji Xia, 10/29/2012 12:56 -- Created document.