Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-070 | 13th May 2021 19:28

#### SOS lower bound for exact planted clique

TR21-070
Authors: Shuo Pang
Publication: 13th May 2021 20:19
We prove a SOS degree lower bound for the planted clique problem on Erd{\"o}s-R\'enyi random graphs $G(n,1/2)$. The bound we get is degree $d=\Omega(\epsilon^2\log n/\log\log n)$ for clique size $\omega=n^{1/2-\epsilon}$, which is almost tight. This improves the result of \cite{barak2019nearly} on the soft'' version of the problem, where the family of equality-axioms generated by $x_1+...+x_n=\omega$ was relaxed to one inequality $x_1+...+x_n\geq\omega$.
As a technical by-product, we also naturalize'' previous techniques developed for the soft problem. This includes a new way of defining the pseudo-expectation and a more robust method to solve the coarse diagonalization of the moment matrix.