Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006) establish a beautiful picture for the computational complexity of approximating the partition function of the hard-core model. Let $\lambda_c(T_\Delta)$ denote the critical activity for the hard-model on the infinite $\Delta$-regular tree. Weitz presented an FPTAS …