License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2020.4
URN: urn:nbn:de:0030-drops-125564
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12556/
Go to the corresponding LIPIcs Volume Portal

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

Approximability of the Eight-Vertex Model

pdf-format:
LIPIcs-CCC-2020-4.pdf (2 MB)

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.

BibTeX - Entry

@InProceedings{cai_et_al:LIPIcs:2020:12556,
  author =	{Jin-Yi Cai and Tianyu Liu and Pinyan Lu and Jing Yu},
  title =	{{Approximability of the Eight-Vertex Model}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{4:1--4:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Shubhangi Saraf},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12556},
  URN =		{urn:nbn:de:0030-drops-125564},
  doi =		{10.4230/LIPIcs.CCC.2020.4},
  annote =	{Keywords: Approximate complexity, the eight-vertex model, Markov chain Monte Carlo}
}

Keywords: Approximate complexity, the eight-vertex model, Markov chain Monte Carlo
Collection: 35th Computational Complexity Conference (CCC 2020)
Issue Date: 2020
Date of publication: 17.07.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI