The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω log (n) added to an Erdős-Rényi graph G ∼ G(n,1 2 ), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size ω = Ω(n). By contrast, information theoretically, one can recover planted cliques so long as ω log (n). In this work, we continue the investigation of algorithms from the Sum of Squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson  and Deshpande and Montanari . Our main result is that degree four SoS does not recover the planted clique unless ω n/ polylog n, improving on the bound ω n1/3 due to Reference . An argument of Kelner shows that the this result cannot be proved using the same certificate as prior works. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by “correcting” the certificate of References [2, 25, 27].
All Science Journal Classification (ASJC) codes
- Mathematics (miscellaneous)
- Planted clique
- Random matrices
- Sum of Squares method