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

被引：27

作者：

Cai, Jin-Yi ^{[1
]}

Galanis, Andreas ^{[2
]}

Goldberg, Leslie Ann ^{[2
]}

Guo, Heng ^{[1
]}

Jerrum, Mark ^{[3
]}

Stefankovic, Daniel ^{[4
]}

Vigoda, Eric ^{[5
]}

机构：

[1] Univ Wisconsin, Dept Comp Sci, 1210 W Dayton St, Madison, WI 53706 USA

[2] Univ Oxford, Dept Comp Sci, Wolfson Bldg,Pk Rd, Oxford OX1 3QD, England

[3] Univ London, Sch Math Sci, Queen Mary, Mile End Rd, London E1 4NS, England

[4] Univ Rochester, Dept Comp Sci, Rochester, NY 14627 USA

[5] Georgia Inst Technol, Sch Comp Sci, Atlanta, GA 30332 USA

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2016年 / 82卷 / 05期

基金：

美国国家科学基金会; 欧洲研究理事会;

关键词：

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

D O I：

10.1016/j.jcss.2015.11.009

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：690 / 711

页数：22

共 31 条

[1]

Bulatov A. A., 2013, J ACM, V60

[2]

Bulatov AA, 2008, LECT NOTES COMPUT SC, V5125, P646, DOI 10.1007/978-3-540-70575-8_53

[3]

Cai JY, 2012, STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, P909

[4]

Cai JY, 2009, ACM S THEORY COMPUT, P715

[5]

Chen X., 2013, STACS, P148

[6] Kahler-Einstein Metrics and Stability [J].

Chen, Xiuxiong ;

Donaldson, Simon ;

Sun, Song .

INTERNATIONAL MATHEMATICS RESEARCH NOTICES, 2014, 2014 (08) :2119-2125

[7] The relative complexity of approximate counting problems [J].

Dyer, M ;

Goldberg, LA ;

Greenhill, C ;

Jerrum, M .

ALGORITHMICA, 2004, 38 (03) :471-500

[8] AN EFFECTIVE DICHOTOMY FOR THE COUNTING CONSTRAINT SATISFACTION PROBLEM [J].

Dyer, Martin ;

Richerby, David .

SIAM JOURNAL ON COMPUTING, 2013, 42 (03) :1245-1274

[9] An approximation trichotomy for Boolean #CSP [J].

Dyer, Martin ;

Goldberg, Leslie Ann ;

Jerrum, Mark .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2010, 76 (3-4) :267-277

[10]

Galanis Andreas, 2011, Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques. Proceedings 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, P567, DOI 10.1007/978-3-642-22935-0_48

← 1 2 3 4 →