2015/07/18 by Prasad Raghavendra, Raghavendra, Prasad, Tselil Schramm +1 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1507.05136
openalex publication_date 2015/07/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a lower bound of Ω(√(n)) for the degree-4 Sum-of-Squares SDP relaxation for the planted clique problem. Specifically, we show that on an Erdös-Rényi graph G(n,\tfrac12), with high probability there is a feasible point for the degree-4 SOS relaxation of the clique problem with an objective value of Ω(√(n)), so that the program cannot distinguish between a random graph and a random graph with a planted clique of size O(√(n)). This bound is tight. We build on the works of Deshpande and Montanari and Meka et al., who give lower bounds of Ω(n1/3) and Ω(n1/4) respectively. We improve on their results by making a perturbation to the SDP solution proposed in their work, then showing that this perturbation remains PSD as the objective value approaches Ω(n1/2). In an independent work, Hopkins, Kothari and Potechin [HKP15] have obtained a similar lower bound for the degree-4 SOS relaxation.