#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Jin-Yi Cai; Andreas Galanis; Leslie Ann Goldberg; Heng Guo; Mark Jerrum; Daniel Stefankovic; Eric Vigoda

doi:10.1016/j.jcss.2015.11.009

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Jin-Yi Cai, Andreas Galanis^*, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1016/j.jcss.2015.11.009
Publication status	Published - Aug 2016

Keywords / Materials (for Non-textual outputs)

Spin systems
Approximate counting
Complexity
#BIS-hardness
Phase transition
COMPLEXITY

Access to Document

10.1016/j.jcss.2015.11.009

bis2spin-JCSS-08-09-2015Accepted author manuscript, 325 KBLicence: Creative Commons: Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

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)

Cite this

@article{fb9e7b6c483b41a880e19ac16f012361,

title = "#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region",

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.",

keywords = "Spin systems, Approximate counting, Complexity, #BIS-hardness, Phase transition, COMPLEXITY",

author = "Jin-Yi Cai and Andreas Galanis and Goldberg, {Leslie Ann} and Heng Guo and Mark Jerrum and Daniel Stefankovic and Eric Vigoda",

year = "2016",

month = aug,

doi = "10.1016/j.jcss.2015.11.009",

language = "English",

volume = "82",

pages = "690--711",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press",

number = "5",

}

TY - JOUR

T1 - #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

AU - Cai, Jin-Yi

AU - Galanis, Andreas

AU - Goldberg, Leslie Ann

AU - Guo, Heng

AU - Jerrum, Mark

AU - Stefankovic, Daniel

AU - Vigoda, Eric

PY - 2016/8

Y1 - 2016/8

N2 - 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.

AB - 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.

KW - Spin systems

KW - Approximate counting

KW - Complexity

KW - #BIS-hardness

KW - Phase transition

KW - COMPLEXITY

U2 - 10.1016/j.jcss.2015.11.009

DO - 10.1016/j.jcss.2015.11.009

M3 - Article

SN - 0022-0000

VL - 82

SP - 690

EP - 711

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 5

ER -

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

Abstract

Keywords / Materials (for Non-textual outputs)

Access to Document

Fingerprint

Profiles

Heng Guo

Cite this