#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 journalArticlepeer-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 languageEnglish
Pages (from-to)690-711
Number of pages22
JournalJournal of Computer and System Sciences
Volume82
Issue number5
DOIs
Publication statusPublished - Aug 2016

Keywords

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

Cite this