## 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 language | English (US) |
---|---|

Article number | 6375314 |

Pages (from-to) | 361-369 |

Number of pages | 9 |

Journal | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |

DOIs | |

State | Published - 2012 |

Externally published | Yes |

Event | 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States Duration: Oct 20 2012 → Oct 23 2012 |

## All Science Journal Classification (ASJC) codes

- General Computer Science

## Keywords

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