#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region |
| |
| Affiliation: | 1. Department of Computer Sciences, University of Wisconsin–Madison, Madison, WI 53706, USA;2. Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK;3. School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London E1 4NS, UK;4. Department of Computer Science, University of Rochester, Rochester, NY 14627, USA;5. School of Computer Science, Georgia Institute of Technology, Atlanta, GA 30332, USA |
| |
| Abstract: | Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #Sat to approximate. We study #BIS in the general framework of two-state spin systems on bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. Consequently, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs. |
| |
| Keywords: | Spin systems Approximate counting Complexity #BIS-hardness Phase transition |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
