#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
作者：
Highlights：
• We examine the problem of approximating the partition function in 2-spin systems.
• We define: nearly-independent phase-correlated spins, unary symmetry breaking.
• If these hold, the problem is as hard as counting bipartite independent sets (#BIS).
• We thus classify antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.
• The uniqueness threshold on the infinite regular tree captures the classification.
摘要
•We examine the problem of approximating the partition function in 2-spin systems.•We define: nearly-independent phase-correlated spins, unary symmetry breaking.•If these hold, the problem is as hard as counting bipartite independent sets (#BIS).•We thus classify antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.•The uniqueness threshold on the infinite regular tree captures the classification.
论文关键词：Spin systems,Approximate counting,Complexity,#BIS-hardness,Phase transition
论文评审过程：Received 18 September 2014, Revised 20 September 2015, Accepted 12 November 2015, Available online 2 December 2015, Version of Record 1 April 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2015.11.009
