A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

Boaz Barak, Samuel B. Hopkins, Jonathan Kelner +3

We prove that with high probability over the choice of a random graph $G$ from the Erdős-Rényi distribution $G(n,1/2)$, the $n^{O(d)}$-time degree $d$ Sum-of-Squares semidefinite p…