Saraf, Shubhangi
(Ed.)

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.

more »
« less