Theory Seminar: Approximability of the Six-vertex Model

Friday, December 1, 2017 - 2:30pm
CS 4310

Speaker Name: 

Tianyu Liu

Speaker Institution: 

UW-Madison

Cookies: 

No

Description: 

Six-vertex models originate in statistical mechanics, as a family of vertex models for crystal lattices with hydrogen bonds. In the language of graph theory and theory of computing, it is a sum-of-product computation, where on a 4-regular graph, we compute a partition function which is a weighted sum of Eulerian orientations, where at every vertex, the orientation must be two-in-two-out (called ice rule). There are thousands of papers on the six-vertex model, making it one of the three most studied models in statistical physics, together with ferromagnetic Ising and monomer-dimer models.

In joint work with Jin-Yi Cai and Pinyan Lu, we take the first step toward a classification of the approximation complexity of the six-vertex model. Our complexity results conform to the phase transition phenomenon from physics. We show that the approximation complexity of the six-vertex model behaves dramatically differently on the two sides separated by the phase transition threshold. Furthermore, we present structural properties of the six-vertex model on planar graphs for parameter settings that have known relations to the Tutte polynomial T(G;x,y). In this talk, I will outline our main results and techniques in this work.