期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove a SOS degree lower bound for the planted clique problem on Erd{\"o}s-R\'enyi random graphs G(n12) . The bound we get is degree d=(2lognloglogn) for clique size =n12− , 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 x1++xn= was relaxed to one inequality x1++xn . 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.
