@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.}",

note = "Publisher Copyright: {\textcopyright} Copyright 2015 ACM.; 47th Annual ACM Symposium on Theory of Computing, STOC 2015 ; Conference date: 14-06-2015 Through 17-06-2015",

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",

}