Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-070 | 13th May 2021 19:28

SOS lower bound for exact planted clique

RSS-Feed




TR21-070
Authors: Shuo Pang
Publication: 13th May 2021 20:19
Downloads: 764
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.



ISSN 1433-8092 | Imprint