Journal article icon

Journal article

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

Expand abstract
Publication status:
Accepted
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Expand authors...
More from this funder
Grant:
CCF-1217549; CCF-1318374; CCF-1217458
Publisher:
Pleiades Publishing Publisher's website
Journal:
Journal of Computer and Systems Sciences International Journal website
Publication date:
2015-01-01
EISSN:
1555-6530
ISSN:
1064-2307
URN:
uuid:5be4e409-54cb-47eb-b3cb-e41b27ff4ee9
Source identifiers:
577323
Local pid:
pubs:577323

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP