Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

Heng Guo; Pinyan Lu

Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

Research output: Contribution to journal › Article › peer-review

Abstract

We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin systems in certain parameter regimes. The threshold we obtain is almost tight up to an integrality gap. Our technique is based on the correlation decay framework. The main technical contribution is a new potential function, with which we establish a new kind of spatial mixing

Original language	English
Number of pages	27
Journal	ACM Transactions on Computation Theory
Publication status	Accepted/In press - 5 Jul 2018

Access to Document

Ferro2spin_ToCTAccepted author manuscript, 237 KBLicence: Creative Commons: Attribution (CC-BY)

Cite this

@article{24cf733992fa4d0fabd49d57646b0461,

title = "Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems",

abstract = "We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin systems in certain parameter regimes. The threshold we obtain is almost tight up to an integrality gap. Our technique is based on the correlation decay framework. The main technical contribution is a new potential function, with which we establish a new kind of spatial mixing",

author = "Heng Guo and Pinyan Lu",

year = "2018",

month = jul,

day = "5",

language = "English",

journal = "ACM Transactions on Computation Theory",

issn = "1942-3454",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

T1 - Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

AU - Guo, Heng

AU - Lu, Pinyan

PY - 2018/7/5

Y1 - 2018/7/5

N2 - We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin systems in certain parameter regimes. The threshold we obtain is almost tight up to an integrality gap. Our technique is based on the correlation decay framework. The main technical contribution is a new potential function, with which we establish a new kind of spatial mixing

AB - We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin systems in certain parameter regimes. The threshold we obtain is almost tight up to an integrality gap. Our technique is based on the correlation decay framework. The main technical contribution is a new potential function, with which we establish a new kind of spatial mixing

M3 - Article

JO - ACM Transactions on Computation Theory

JF - ACM Transactions on Computation Theory

SN - 1942-3454

ER -

Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

Abstract

Access to Document

Fingerprint

Cite this