Tight Lower Bounds for Planted Clique in the Degree-4 SOS Program

Prasad Raghavendra, Tselil Schramm

We give a lower bound of $\tilde{\Omega }(\sqrt{n})$ for the degree-4 Sum-of-Squares SDP relaxation for the planted clique problem. Specifically, we show that on an Erdös-Rényi graph $G(n,…