Approximating the partition function of planar two-state spin systems
arXiv:1208.4987 · doi:10.1016/j.jcss.2014.06.007
Abstract
We consider the problem of approximating the partition function of the hard-core model on planar graphs of degree at most 4. We show that when the activity lambda is sufficiently large, there is no fully polynomial randomised approximation scheme for evaluating the partition function unless NP=RP. The result extends to a nearby region of the parameter space in a more general two-state spin system with three parameters. We also give a polynomial-time randomised approximation scheme for the logarithm of the partition function.
References in corpus (5)
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- Approximating the partition function of the ferromagnetic Potts model
- Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model
- Correlation Decay up to Uniqueness in Spin Systems
- Approximate Counting via Correlation Decay on Planar Graphs