2015/06/03 by Raghu Meka, Aaron Potechin, Avi Wigderson · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Advanced Graph Theory Research #Combinatorics #Mathematics #Clique #Clique problem #Hierarchy #Upper and lower bounds #Random graph #Explained sum of squares #Discrete mathematics #Graph #Time complexity #Chordal graph #Statistics
paper · doi:10.1145/2746539.2746600
openalex publication_date 2015/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for k = Θ(√n). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-Of-Squares hierarchy. We prove the first average case lower bound for this model: for almost all graphs in G(n,1/2), r rounds of the SOS hierarchy cannot find a planted k-clique unless k ≥ (√n/log n)1/rCr. Thus, for any constant number of rounds planted cliques of size no(1) cannot be found by this powerful class of algorithms. This is shown via an integrability gap for the natural formulation of maximum clique problem on random graphs for SOS and Lasserre hierarchies, which in turn follow from degree lower bounds for the Positivestellensatz proof system.