Speaker:
Allan Sly
Title:
The complexity of counting for anti-ferromagnetic 2-spin systems
Abstract:
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