Speaker:
Andreas Galanis
Title:
Inapproximability of the antiferromagnetic Ising model in Two Moments
Abstract:
Inapproximability results of Sly (2010), together with an approximation algorithm
presented by Weitz (2006), established precisely a computational transition for
the approximability of the partition function in the hard-core model in graphs of
constant maximum degree Delta. This transition coincides with the phase transition
on the infinite Delta-regular tree.
We focus on proving inapproximability for a more general class of 2-spin models
when the parameters lie in the non-uniqueness regime of the infinite Delta-regular tree,
including the antiferromagnetic Ising model without external field. This is
accomplished by a careful analysis of the models on random bipartite Delta-regular
graphs, using first and second moment arguments. The purpose of this talk is to convey
the key ideas in such a scheme and display how to harness the main technical challenges.
Joint work with Daniel Stefankovic and Eric Vigoda (2012).