Document Open Access Logo

Approximability of the Eight-Vertex Model

Authors Jin-Yi Cai, Tianyu Liu, Pinyan Lu, Jing Yu

PDF
Thumbnail PDF

File

LIPIcs.CCC.2020.4.pdf
  • Filesize: 2.35 MB
  • 18 pages

Document Identifiers

Author Details

Jin-Yi Cai
  • University of Wisconsin-Madison, WI, USA
Tianyu Liu
  • University of Wisconsin-Madison, WI, USA
Pinyan Lu
  • Shanghai University of Finance and Economics, China
Jing Yu
  • Georgia Institute of Technology, Atlanta, GA, USA

Funding

  • Cai, Jin-Yi: Supported by NSF CCF-1714275.
  • Liu, Tianyu: Supported by NSF CCF-1714275.

Cite AsGet BibTex

Jin-Yi Cai, Tianyu Liu, Pinyan Lu, and Jing Yu. Approximability of the Eight-Vertex Model. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.CCC.2020.4

Abstract

We initiate a study of the classification of approximation complexity of the eight-vertex model defined over 4-regular graphs. The eight-vertex model, together with its special case the six-vertex model, is one of the most extensively studied models in statistical physics, and can be stated as a problem of counting weighted orientations in graph theory. Our result concerns the approximability of the partition function on all 4-regular graphs, classified according to the parameters of the model. Our complexity results conform to the phase transition phenomenon from physics. We introduce a quantum decomposition of the eight-vertex model and prove a set of closure properties in various regions of the parameter space. Furthermore, we show that there are extra closure properties on 4-regular planar graphs. These regions of the parameter space are concordant with the phase transition threshold. Using these closure properties, we derive polynomial time approximation algorithms via Markov chain Monte Carlo. We also show that the eight-vertex model is NP-hard to approximate on the other side of the phase transition threshold.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Approximate complexity
  • the eight-vertex model
  • Markov chain Monte Carlo

Metrics

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

Related Versions

References

  1. G. T. Barkema and M. E. J. Newman. Monte carlo simulation of ice models. Phys. Rev. E, pages 1155-1166, 1998. Google Scholar
  2. R. J. Baxter. Exactly Solved Models in Statistical Mechanics. Academic Press Inc., San Diego, CA, USA, 1982. Google Scholar
  3. Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5), October 2013. URL: https://doi.org/10.1145/2528400.
  4. Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems, volume 1. Cambridge University Press, 2017. URL: https://doi.org/10.1017/9781107477063.
  5. Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3), June 2017. URL: https://doi.org/10.1145/2822891.
  6. Jin-Yi Cai and Zhiguo Fu. Complexity classification of the eight-vertex model. CoRR, abs/1702.07938, 2017. URL: http://arxiv.org/abs/1702.07938.
  7. Jin-Yi Cai and Artem Govorov. Perfect matchings, rank of connection tensors and graph homomorphisms. In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 476-495, 2019. URL: https://doi.org/10.1137/1.9781611975482.30.
  8. Jin-Yi Cai and Tianyu Liu. Counting perfect matchings and the eight-vertex model. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, ICALP '20, pages 23:1-23:19, 2020. URL: http://arxiv.org/abs/1904.10493.
  9. Jin-Yi Cai, Tianyu Liu, and Pinyan Lu. Approximability of the six-vertex model. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 2248-2261, 2019. URL: https://doi.org/10.1137/1.9781611975482.136.
  10. Jin-Yi Cai, Tianyu Liu, Pinyan Lu, and Jing Yu. Approximability of the eight-vertex model, 2018. URL: http://arxiv.org/abs/1811.03126.
  11. Jin-Yi Cai, Pinyan Lu, and Mingji Xia. The complexity of complex weighted Boolean #CSP. Journal of Computer and System Sciences, 80(1):217-236, 2014. URL: https://doi.org/10.1016/j.jcss.2013.07.003.
  12. Martin Dyer, Alan Frieze, and Ravi Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1-17, January 1991. URL: https://doi.org/10.1145/102782.102783.
  13. Martin Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM Journal on Computing, 42(3):1245-1274, 2013. URL: https://doi.org/10.1137/100811258.
  14. Michael Freedman, László Lovász, and Alexander Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society, 20:37-51, 2007. URL: https://doi.org/10.1090/S0894-0347-06-00529-7.
  15. Sam Greenberg and Dana Randall. Slow mixing of Markov chains using fault lines and fat contours. Algorithmica, 58(4):911-927, December 2010. URL: https://doi.org/10.1007/s00453-008-9246-3.
  16. Mark Jerrum. Counting, Sampling and Integrating: Algorithm and Complexity. Birkhäuser, Basel, 2003. Google Scholar
  17. Mark Jerrum and Alistair Sinclair. Approximating the permanent. SIAM Journal on Computing, 18(6):1149-1178, 1989. URL: https://doi.org/10.1137/0218077.
  18. Mark R. Jerrum, Leslie G. Valiant, and Vijay V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43(Supplement C):169-188, 1986. URL: https://doi.org/10.1016/0304-3975(86)90174-X.
  19. Richard M. Karp and Michael Luby. Monte-Carlo algorithms for enumeration and reliability problems. In Proceedings of the 24th Annual Symposium on Foundations of Computer Science, SFCS '83, pages 56-64, Washington, DC, USA, 1983. IEEE Computer Society. URL: https://doi.org/10.1109/SFCS.1983.35.
  20. W.B.Raymond Lickorish. An Introduction to Knot Theory. Springer New York, 1997. URL: https://books.google.com/books?id=PhHhw_kRvewC.
  21. Aneesur Rahman and Frank H. Stillinger. Proton distribution in ice and the kirkwood correlation factor. The Journal of Chemical Physics, 57(9):4009-4017, 1972. URL: https://doi.org/10.1063/1.1678874.
  22. Alistair Sinclair. Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing, 1:351-370, 1992. Google Scholar
  23. Olav F. Syljuåsen and M. B. Zvonarev. Directed-loop monte carlo simulations of vertex models. Phys. Rev. E, 70:016118, July 2004. URL: https://doi.org/10.1103/PhysRevE.70.016118.
  24. A. Yanagawa and J.F. Nagle. Calculations of correlation functions for two-dimensional square ice. Chemical Physics, 43(3):329-339, 1979. URL: https://doi.org/10.1016/0301-0104(79)85201-5.
  25. Mihalis Yannakakis. Node- and edge-deletion NP-complete problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC '78, pages 253-264, 1978. URL: https://doi.org/10.1145/800133.804355.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact