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 条

[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
Goemans, MX
Williamson, DP
[J]. JOURNAL OF THE ACM, 1995, 42 (06) : 1115 - 1145
[15] Complexity of Positivstellensatz proofs for the knapsack
Grigoriev, D
[J]. COMPUTATIONAL COMPLEXITY, 2001, 10 (02) : 139 - 154
[16] Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
Grigoriev, D
[J]. THEORETICAL COMPUTER SCIENCE, 2001, 259 (1-2) : 613 - 622
[17] Khot S, 2002, ANN IEEE CONF COMPUT, P25
[18] Global optimization with polynomials and the problem of moments
Lasserre, JB
[J]. SIAM JOURNAL ON OPTIMIZATION, 2001, 11 (03) : 796 - 817
[19] Nesterov Y., 2000, High Performance Optimization, V33, P405, DOI DOI 10.1007/978-1-4757-3216-0_17
[20] Goldreich's PRG: Evidence for near-optimal polynomial stretch
O'Donnell, Ryan
Witmer, David
[J]. 2014 IEEE 29TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 2014, : 1 - 12

← 1 2 3 →