__
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

Downloads: 694

Keywords:

**Abstract:**
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.