Sum of Squares Lower Bounds from Pairwise Independence

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.