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

Understand

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\"os-R\'enyi graph $G(n,\tfrac{1}{2})$, with high probability there is a feasible point for the degree-4 SOS relaxation of the clique problem with an objective value of $\tilde{\Omega}(\sqrt{n})$, so that the program cannot distinguish between a random graph and a random graph with a planted clique of size $\tilde{O}(\sqrt{n})$.
• This bound is tight.
• We build on the works of Deshpande and Montanari and Meka et al., who give lower bounds of $\tilde{\Omega}(n^{1/3})$ and $\tilde{\Omega}(n^{1/4})$ respectively.