Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models

Andreas Galanis, Daniel Stefankovic, Eric Vigoda

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006) establish a beautiful picture for the computational complexity of…