The complexity of counting for anti-ferromagnetic 2-spin systems

Allan Sly
University of California, Berkeley (UC Berkeley)
Theory group

I will discuss new methods for approximating the log partition function of anti-ferromagnetic 2-spin systems on locally treelike bi-partite graphs.
As a consequence we show that approximating the partition function is NP-hard for anti-ferromagnetic 2-spin systems in the non-uniqueness regime.

Joint work with Nike Sun


Back to Mathematical Challenges in Graphical Models and Message-Passing Algorithms