Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models

Details 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

2012-03-10

arxiv.org/abs/1203.2226v2

Computer Science

Discrete Mathematics

49 pages

Scientific paper

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 for the partition function when $\lambda<\lambda_c(T_\Delta)$ for graphs with constant maximum degree $\Delta$. In contrast, Sly showed that for all $\Delta\geq 3$, there exists $\epsilon_\Delta>0$ such that (unless RP=NP) there is no FPRAS for approximating the partition function on graphs of maximum degree $\Delta$ for activities $\lambda$ satisfying $\lambda_c(T_\Delta)<\lambda<\lambda_c(T_\Delta)+\epsilon_\Delta$. We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Recent results of Li et al. and Sinclair et al. extend Weitz's approach to any 2-spin model, which includes the antiferromagnetic Ising model, to yield an FPTAS for the partition function for all graphs of constant maximum degree $\Delta$ when the parameters of the model lie in the uniqueness regime of the infinite tree $T_\Delta$. We prove the complementary result that for the antiferrogmanetic Ising model without external field that, unless RP=NP, for all $\Delta\geq 3$, there is no FPRAS for approximating the partition function on graphs of maximum degree $\Delta$ when the inverse temperature lies in the non-uniqueness regime of the infinite tree $T_\Delta$. Our results extend to a region of the parameter space for general 2-spin models. Our proof works by relating certain second moment calculations for random $\Delta$-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.

Affiliated with

Also associated with

No associations

Rating

Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-488343