Mathematics – Probability
Scientific paper
2012-03-12
Mathematics
Probability
23 pages
Scientific paper
The class of two-spin systems contains several important models, including random independent sets and the Ising model of statistical physics. We show that for both the hard-core (independent set) model and the anti-ferromagnetic Ising model with arbitrary external field, it is NP-hard to approximate the partition function or approximately sample from the model on d-regular graphs when the model has non-uniqueness on the d-regular tree. Together with results of Jerrum--Sinclair, Weitz, and Sinclair--Srivastava--Thurley giving FPRAS's for all other two-spin systems except at the uniqueness threshold, this gives an almost complete classification of the computational complexity of two-spin systems on bounded-degree graphs. Our proof establishes that the normalized log-partition function of any two-spin system on bipartite locally tree-like graphs converges to a limiting "free energy density" which coincides with the (non-rigorous) Bethe prediction of statistical physics. We use this result to characterize the local structure of two-spin systems on locally tree-like bipartite expander graphs, which then become the basic gadgets in a randomized reduction to approximate MAX-CUT. Our approach is novel in that it makes no use of the second moment method employed in previous works on these questions.
Sly Allan
Sun Nike
No associations
LandOfFree
The computational hardness of counting in two-spin models on d-regular graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The computational hardness of counting in two-spin models on d-regular graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The computational hardness of counting in two-spin models on d-regular graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-489269