ECCC-Report TR21-070https://eccc.weizmann.ac.il/report/2021/070Comments and Revisions published for TR21-070en-usThu, 13 May 2021 20:19:11 +0300
Paper TR21-070
| SOS lower bound for exact planted clique |
Shuo Pang
https://eccc.weizmann.ac.il/report/2021/070We 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.Thu, 13 May 2021 20:19:11 +0300https://eccc.weizmann.ac.il/report/2021/070