Abstract
There has been great progress in classifying the approximation complexity of anti-ferro 2-spin systems. We will first review these results, and then talk about some new results regarding ferro 2-spin systems. In particular, we conjecture a complexity transition threshold that is almost tight for ferro systems. We confirm the conjecture for some range of the parameters and provide evidence for the rest. In addition we will show some (hardness) results when going beyond non-negative weights to complex weights.
It includes joint work with Pinyan Lu and Leslie Goldberg.