Sum of Squares Lower Bounds from Pairwise Independence

被引：19

作者：

Barak, Boaz ^{[1
]}

Chan, Siu On ^{[1
]}

Kothari, Pravesh K. ^{[2
]}

机构：

[1] Microsoft Res, Redmond, WA 98052 USA

[2] UT Austin, Austin, TX USA

来源：

STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2015年

关键词：

Sum of Squares Hierarchy; CSPs; lower bounds; ALGORITHMS; PROOFS; GAPS;

D O I：

10.1145/2746539.2746625

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that for every epsilon > 0 and predicate P : {0, 1}(k) -> {0, 1} that supports a pairwise independent distribution, there exists an instance / of the MAxP constraint satisfaction problem on n variables such that no assignment can satisfy more than a vertical bar P-1(1)vertical bar/2(k) + epsilon fraction of I's constraints but the degree Omega(n) Sum of Squares semidefinite programming hierarchy cannot certify that I is unsatisfiable. Similar results were previously only known for weaker hierarchies.

引用

页码：97 / 106

页数：10

共 27 条

[1] [Anonymous], 2014, LECT NOTES MIT SEMIN
[2] Arora S., 2006, THEORY COMPUTING, V2, P19, DOI DOI 10.4086/toc.2006.v002a002
[3] RANDOMLY SUPPORTED INDEPENDENCE AND RESISTANCE
Austrin, Per
Hastad, Johan
[J]. SIAM JOURNAL ON COMPUTING, 2011, 40 (01) : 1 - 27
[4] APPROXIMATION RESISTANT PREDICATES FROM PAIRWISE INDEPENDENCE
Austrin, Per
Mossel, Elchanan
[J]. COMPUTATIONAL COMPLEXITY, 2009, 18 (02) : 249 - 271
[5] Rounding Sum-of-Squares Relaxations
Barak, Boaz
Kelner, Jonathan A.
Steurer, David
[J]. STOC'14: PROCEEDINGS OF THE 46TH ANNUAL 2014 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2014, : 31 - 40
[6] Barak B, 2012, STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, P307
[7] Barak Boaz, 2013, INNOVATIONS THEORETI, P197, DOI DOI 10.1145/2422436.2422460
[8] Barak Boaz, 2014, P INT C MATH ICM
[9] Benabbas S., 2012, THEORY COMPUTING, V8, P269, DOI DOI 10.4086/TOC.2012.V008A012
[10] Chan SO, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P447

← 1 2 3 →