New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model

We prove a complete complexity classification theorem for the planar eight-vertex model. For every parameter setting in C for the eight-vertex model, the partition function is either (1) computable in P-time for every graph, or (2) #P-hard for general graphs but computable in Ptime for planar graphs, or (3) #P-hard even for planar graphs. The classification has an explicit criterion. In (2), we discover new P-time computable eight-vertex models on planar graphs beyond Kasteleyn's algorithm for counting planar perfect matchings. 1 They are obtained by a combinatorial transformation to the planar Even Coloring problem followed by a holographic transformation to the tractable cases in the planar six-vertex model. In the process, we also encounter non-local connections between the planar eight vertex model and the bipartite Ising model, conformal lattice interpolation and Möbius transformation from complex analysis. The proof also makes use of cyclotomic fields.