EUVIMEDEUVIMED entdecken
Crossref

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

ANDREAS GALANIS, DANIEL ŠTEFANKOVIČ, ERIC VIGODA

Combinatorics, Probability and Computing · 2016-07 · 25 (4) · 500-559

DOI: 10.1017/s0963548315000401 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Combinatorics, Probability and Computing, online erschienen am 02.02.2016. Verfasst von ANDREAS GALANIS und 2 weiteren Autor:innen. Die Arbeit wurde bisher 82-mal zitiert (Crossref) und nennt 33 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006), establish a beautiful picture of the computational complexity of approximating the partition function of the hard-core model. Let λ c ( $\mathbb{T}_{\Delta}$ ) denote the critical activity for the hard-model on the infinite Δ-regular tree. Weitz presented an FPTAS for the partition function when λ < λ c ( $\mathbb{T}_{\Delta}$ ) for graphs with constant maximum degree Δ. In contrast, Sly showed that for all Δ ⩾ 3, there exists ε Δ > 0 such that (unless RP = NP) there is no FPRAS for approximating the partition function on graphs of maximum degree Δ for activities λ satisfying λ c ( $\mathbb{T}_{\Delta}$ ) < λ < λ c ( $\mathbb{T}_{\Delta}$ ) + ε Δ . We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Sinclair, Srivastava and Thurley (2014) extended Weitz's approach to the antiferromagnetic Ising model, yielding an FPTAS for the partition function for all graphs of constant maximum degree Δ when the parameters of the model lie in the uniqueness region of the infinite Δ-regular tree. We prove the complementary result for the antiferromagnetic Ising model without external field, namely, that unless RP = NP, for all Δ ⩾ 3, there is no FPRAS for approximating the partition function on graphs of maximum degree Δ when the inverse temperature lies in the non-uniqueness region of the infinite tree $\mathbb{T}_{\Delta}$ . Our proof works by relating certain second moment calculations for random Δ-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.

Zitieren

APA

GALANIS, A., ŠTEFANKOVIČ, D., & VIGODA, E. (2016). Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models. Combinatorics, Probability and Computing, 25(4), 500-559. https://doi.org/10.1017/s0963548315000401

Vancouver

GALANIS A, ŠTEFANKOVIČ D, VIGODA E. Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models. Combinatorics, Probability and Computing. 2016;25(4):500-559. doi:10.1017/s0963548315000401

BibTeX
@article{GALANIS2016,
  author = {GALANIS, ANDREAS and ŠTEFANKOVIČ, DANIEL and VIGODA, ERIC},
  title = {Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models},
  journal = {Combinatorics, Probability and Computing},
  year = {2016},
  volume = {25},
  number = {4},
  pages = {500--559},
  doi = {10.1017/s0963548315000401}
}
Kostenlos starten →