Abstract
The six-vertex model and its generalization the eight-vertex model originate and are widely studied in statistical physics, as a family of vertex models for crystal lattices with hydrogen bonds. In the language of graph theory, these models are defined over 4-regular graphs. The states of the six-vertex model are (weighted) Eulerian orientations of the underlying graph, and the states of the eight-vertex model are (weighted) even orientations in which there is an even number of arrows into (and out of) each vertex. We study the classification of the approximation complexity of the partition functions of the six- and the eight-vertex models on all 4-regular graphs. Our complexity results conform to the phase transition phenomenon from physics and show tight connections with the complexity of approximate counting perfect matchings (on not necessarily bipartite graphs)---a central open problem in this field. In particular we give a characterization for all arity 4 functions realizable by (non-planar) matchgates, using a geometric proof. In this talk, I will outline some of our findings and techniques.