Sum of squares lower bounds from pairwise independence

Boaz Barak; Siu On Chan; Pravesh K. Kothari

doi:10.1145/2746539.2746625

Sum of squares lower bounds from pairwise independence

Boaz Barak
, Siu On Chan
, Pravesh K. Kothari

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

40 Scopus citations

Abstract

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

Original language	English (US)
Title of host publication	STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
Publisher	Association for Computing Machinery
Pages	97-106
Number of pages	10
ISBN (Electronic)	9781450335362
DOIs	https://doi.org/10.1145/2746539.2746625
State	Published - Jun 14 2015
Externally published	Yes
Event	47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States Duration: Jun 14 2015 → Jun 17 2015

Publication series

Name	Proceedings of the Annual ACM Symposium on Theory of Computing
Volume	14-17-June-2015
ISSN (Print)	0737-8017

Other

Other	47th Annual ACM Symposium on Theory of Computing, STOC 2015
Country/Territory	United States
City	Portland
Period	6/14/15 → 6/17/15

All Science Journal Classification (ASJC) codes

Software

Keywords

CSPs
Lower bounds
Sum of Squares Hierarchy

Access to Document

10.1145/2746539.2746625

Cite this

@inproceedings{02b5b1458df34bb98221868cd2abeebe,

title = "Sum of squares lower bounds from pairwise independence",

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

keywords = "CSPs, Lower bounds, Sum of Squares Hierarchy",

author = "Boaz Barak and Chan, \{Siu On\} and Kothari, \{Pravesh K.\}",

year = "2015",

month = jun,

day = "14",

doi = "10.1145/2746539.2746625",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "97--106",

booktitle = "STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing",

}

Barak, B, Chan, SO & Kothari, PK 2015, Sum of squares lower bounds from pairwise independence. in STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. 14-17-June-2015, Association for Computing Machinery, pp. 97-106, 47th Annual ACM Symposium on Theory of Computing, STOC 2015, Portland, United States, 6/14/15. https://doi.org/10.1145/2746539.2746625

Sum of squares lower bounds from pairwise independence. / Barak, Boaz; Chan, Siu On; Kothari, Pravesh K.
STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing. Association for Computing Machinery, 2015. p. 97-106 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. 14-17-June-2015).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Sum of squares lower bounds from pairwise independence

AU - Barak, Boaz

AU - Chan, Siu On

AU - Kothari, Pravesh K.

PY - 2015/6/14

Y1 - 2015/6/14

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

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

KW - CSPs

KW - Lower bounds

KW - Sum of Squares Hierarchy

UR - https://www.scopus.com/pages/publications/84958754791

UR - https://www.scopus.com/pages/publications/84958754791#tab=citedBy

U2 - 10.1145/2746539.2746625

DO - 10.1145/2746539.2746625

M3 - Conference contribution

AN - SCOPUS:84958754791

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 97

EP - 106

BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015

Y2 - 14 June 2015 through 17 June 2015

ER -

Sum of squares lower bounds from pairwise independence

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this