Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs |
| |
Authors: | Alistair Sinclair Piyush Srivastava Marc Thurley |
| |
Institution: | 1. Soda Hall, University of California Berkeley, Berkeley, CA?, 94720, USA 2. Medallia, Inc., Buenos Aires, Argentina
|
| |
Abstract: | We show that for the anti-ferromagnetic Ising model on the Bethe lattice, weak spatial mixing implies strong spatial mixing. As a by-product of our analysis, we obtain what is to the best of our knowledge the first rigorous proof of the uniqueness threshold for the anti-ferromagnetic Ising model (with non-zero external field) on the Bethe lattice. Following a method due to Weitz 15], we then use the equivalence between weak and strong spatial mixing to give a deterministic fully polynomial time approximation scheme for the partition function of the anti-ferromagnetic Ising model with arbitrary field on graphs of degree at most $d$ , throughout the uniqueness region of the Gibbs measure on the infinite $d$ -regular tree. By a standard correspondence, our results translate to arbitrary two-state anti-ferromagnetic spin systems with soft constraints. Subsequent to a preliminary version of this paper, Sly and Sun 13] have shown that our results are optimal in the sense that, under standard complexity theoretic assumptions, there does not exist a fully polynomial time approximation scheme for the partition function of such spin systems on graphs of maximum degree $d$ for parameters outside the uniqueness region. Taken together, the results of 13] and of this paper therefore indicate a tight relationship between complexity theory and phase transition phenomena in two-state anti-ferromagnetic spin systems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|