Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10332686 | Journal of Computer and System Sciences | 2016 | 22 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Å tefankoviÄ, Eric Vigoda,