Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

Authors Heng Guo, Pinyan Lu



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2016.31.pdf
  • Filesize: 0.63 MB
  • 26 pages

Document Identifiers

Author Details

Heng Guo
Pinyan Lu

Cite AsGet BibTex

Heng Guo and Pinyan Lu. Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 31:1-31:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.31

Abstract

For anti-ferromagnetic 2-spin systems, a beautiful connection has been established, namely that the following three notions align perfectly: the uniqueness in infinite regular trees, the decay of correlations (also known as spatial mixing), and the approximability of the partition function. The uniqueness condition implies spatial mixing, and an FPTAS for the partition function exists based on spatial mixing. On the other hand, non-uniqueness implies some long range correlation, based on which NP-hardness reductions are built. These connections for ferromagnetic 2-spin systems are much less clear, despite their similarities to anti-ferromagnetic systems. The celebrated Jerrum-Sinclair Markov chain [JS93] works even if spatial mixing or uniqueness fails. We provide some partial answers. We use (β,γ) to denote the (+,+) and (−,−) edge interactions and λ the external field, where βγ>1. If all fields satisfy λ<λ_c (assuming β≤γ), where λ_c=(γ/β)^{(Δ_c+1)/2} and Δ_c=(\sqrt{βγ}+1)/(\sqrt{βγ}−1), then a weaker version of spatial mixing holds in all trees. Moreover, if β≤1, then λ<λ_c is sufficient to guarantee strong spatial mixing and FPTAS. This improves the previous best algorithm, which is an FPRAS based on Markov chains and works for λ<γ/β [LLZ14a]. The bound λ_c is almost optimal. When β≤1, uniqueness holds in all infinite regular trees, if and only if λ≤λ^int_c, where λ^int_c=(γ/β)(⌈Δc⌉+1)/2. If we allow fields λ>λ^int′_c, where λ^int′_c=(γ/β)(⌊Δc⌋+2)/2, then approximating the partition function is #BIS-hard.
Keywords
  • Approximate counting; Ising model; Spin systems; Correlation decay

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, and Eric Vigoda. #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. In RANDOM, pages 582-595, 2014. Google Scholar
  2. Jin-Yi Cai and Michael Kowalczyk. Spin systems on k-regular graphs with complex edge functions. Theor. Comput. Sci., 461:2-16, 2012. Google Scholar
  3. Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, and Mark Jerrum. The relative complexity of approximate counting problems. Algorithmica, 38(3):471-500, 2003. Google Scholar
  4. Andreas Galanis, Daniel Štefankovič, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic Ising and Hard-Core models. CoRR,, 2012. URL: http://arxiv.org/abs/1203.2226.
  5. Hans-Otto Georgii. Gibbs Measures and Phase Transitions, volume 9 of De Gruyter Studies in Mathematics. de Gruyter, Berlin, second edition, 2011. Google Scholar
  6. Leslie Ann Goldberg and Mark Jerrum. The complexity of ferromagnetic Ising with local fields. Combinatorics, Probability & Computing, 16(1):43-61, 2007. Google Scholar
  7. Leslie Ann Goldberg, Mark Jerrum, and Mike Paterson. The computational complexity of two-state spin systems. Random Struct. Algorithms, 23(2):133-154, 2003. Google Scholar
  8. Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput., 22(5):1087-1116, 1993. Google Scholar
  9. Mark Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci., 43:169-188, 1986. Google Scholar
  10. Frank P. Kelly. Stochastic models of computer communication systems. Journal of the Royal Statistical Society. Series B (Methodological), 47(3):379-395, 1985. Google Scholar
  11. Liang Li, Pinyan Lu, and Yitong Yin. Approximate counting via correlation decay in spin systems. In SODA, pages 922-940, 2012. Google Scholar
  12. Liang Li, Pinyan Lu, and Yitong Yin. Correlation decay up to uniqueness in spin systems. In SODA, pages 67-84, 2013. Google Scholar
  13. Jingcheng Liu, Pinyan Lu, and Chihao Zhang. The complexity of ferromagnetic two-spin systems with external fields. In RANDOM, pages 843-856, 2014. Google Scholar
  14. Russell Lyons. The Ising model and percolation on trees and tree-like graphs. Comm. Math. Phys., 125(2):337-353, 1989. Google Scholar
  15. Elchanan Mossel and Allan Sly. Exact thresholds for Ising-Gibbs samplers on general graphs. Annals of Probability, 41(1):294-328, 2013. Google Scholar
  16. Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič, and Yitong Yin. Spatial mixing and the connective constant: Optimal bounds. In SODA, pages 1549-1563, 2015. Google Scholar
  17. Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs. In SODA, pages 941-953, 2012. Google Scholar
  18. Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. The Annals of Probability, 42(6):2383-2416, 2014. Google Scholar
  19. Dror Weitz. Counting independent sets up to the tree threshold. In STOC, pages 140-149, 2006. Google Scholar
  20. Jinshan Zhang, Heng Liang, and Fengshan Bai. Approximating partition functions of the two-state spin system. Inf. Process. Lett., 111(14):702-710, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail