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. (C) 2015 Elsevier Inc. All rights reserved.
Original language | English |
---|---|
Pages (from-to) | 690-711 |
Number of pages | 22 |
Journal | Journal of Computer and System Sciences |
Volume | 82 |
Issue number | 5 |
DOIs | |
Publication status | Published - Aug 2016 |
Keywords / Materials (for Non-textual outputs)
- Spin systems
- Approximate counting
- Complexity
- #BIS-hardness
- Phase transition
- COMPLEXITY
Fingerprint
Dive into the research topics of '#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region'. Together they form a unique fingerprint.Profiles
-
Heng Guo
- School of Informatics - Reader in Algorithms and Complexity
- Laboratory for Foundations of Computer Science - Lecturer in Algorithms and Complexity
- Foundations of Computation
Person: Academic: Research Active (Teaching)