Sum of squares lower bounds from pairwise independence

Boaz Barak, Siu On Chan, Pravesh K. Kothari

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 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)|/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.

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages97-106
Number of pages10
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
CountryUnited States
CityPortland
Period6/14/156/17/15

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • CSPs
  • Lower bounds
  • Sum of Squares Hierarchy

Fingerprint Dive into the research topics of 'Sum of squares lower bounds from pairwise independence'. Together they form a unique fingerprint.

Cite this