Name
Title | ||
|---|---|---|
Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models |
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1017/s0963548315000401 | Combinatorics, Probability & Computing |
DocType | Volume | Issue |
Journal | 25 | 04 |
ISSN | Citations | PageRank |
Combinator. Probab. Comp. 25 (2016) 500-559 | 28 | 0.98 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| andreas galanis | 1 | 68 | 15.13 |
| Daniel Stefankovic | 2 | 243 | 28.65 |
| Eric Vigoda | 3 | 747 | 76.55 |