Sum of Squares Lower Bounds from Pairwise Independence

被引：20

作者：

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 条

[11]

Chan Siu On, SUM SQUARES LOWER BO

[12]

Charikar M, 2009, ACM S THEORY COMPUT, P283

[13]

de la Vega WF, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P53

[14] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].