Sum of Squares Lower Bounds from Pairwise Independence

Boaz Barak, Siu On Chan, Pravesh Kothari

We prove that for every $\epsilon >0$ and predicate $P:\{0,1{\}}^k\to \{0,1\}$ that supports a pairwise independent distribution, there exists an instance $\mathcal{I}$ of the $\math…