2026-07-23T03:48:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14300 2024-03-06T10:53:54Z ddc:004 open_access

SOS Lower Bound for Exact Planted Clique Pang, Shuo Sum-of-Squares planted clique random graphs average-case lower bound We prove a SOS degree lower bound for the planted clique problem on the Erdös-Rényi random graph G(n,1/2). The bound we get is degree d = Ω(ε²log n/log log n) for clique size ω = n^{1/2-ε}, which is almost tight. This improves the result of [Barak et al., 2019] for the "soft" version of the problem, where the family of the equality-axioms generated by x₁+...+x_n = ω is relaxed to one inequality x₁+...+x_n ≥ ω. As a technical by-product, we also "naturalize" certain techniques that were developed and used for the relaxed problem. This includes a new way to define the pseudo-expectation, and a more robust method to solve out the coarse diagonalization of the moment matrix. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shuo Pang 2021 Is Part Of LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2021.26 urn:nbn:de:0030-drops-143000 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.26 eng https://creativecommons.org/licenses/by/4.0/legalcode