The computational hardness of counting in two-spin models on d-regular graphs

Allan Sly, Nike Sun

Research output: Contribution to journalConference articlepeer-review

71 Scopus citations

Abstract

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 regular graphs when the model has non-uniqueness on the corresponding 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) Be the 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.

Original languageEnglish (US)
Article number6375314
Pages (from-to)361-369
Number of pages9
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - Dec 1 2012
Externally publishedYes
Event53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States
Duration: Oct 20 2012Oct 23 2012

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Bethe free energy
  • Ising model
  • hard-core model
  • independent set
  • spin system

Fingerprint Dive into the research topics of 'The computational hardness of counting in two-spin models on d-regular graphs'. Together they form a unique fingerprint.

Cite this