Siu On Chan: Sum of Squares Lower Bounds from Pairwise Independence

Wednesday, May 6, 2015 - 4:00pm to 5:00pm
Siu On Chan
Microsoft Research

We prove that for every ε > 0 and k-ary predicate P 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.