# Sum-of-squares lower bounds for planted clique

arXiv: https://arxiv.org/abs/1503.06447 · HTML: https://mlsanity.com/paper/1503.06447/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2015.

## Built on by (most cited first, 12 of 12)

- [Clustering a Mixture of Gaussians with Unknown Covariance](https://mlsanity.com/paper/2110.01602/) (2021)
- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs](https://mlsanity.com/paper/2203.02824/) (2022)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy](https://mlsanity.com/paper/2102.08019/) (2021)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Concentration of polynomial random matrices via Efron-Stein inequalities](https://mlsanity.com/paper/2209.02655/) (2022)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [Computational Lower Bounds for Regret Minimization in Normal-Form Games](https://mlsanity.com/paper/2411.01721/) (2024)
- [Recovering Imbalanced Clusters via Gradient-Based Projection Pursuit](https://mlsanity.com/paper/2502.02668/) (2025)

## Abstract (arXiv)

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 ~ sqrt(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^{1/2r} (up to logarithmic factors). Thus, for any constant number of rounds planted cliques of size n^{o(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. We follow the usual recipe for such proofs. First, we introduce a natural "dual certificate" (also known as a "vector-solution" or "pseudo-expectation") for the given system of polynomial equations representing the problem for every fixed input graph. Then we show that the matrix associated with this dual certificate is PSD (positive semi-definite) with high probability over the choice of the input graph.This requires the use of certain tools. One is the theory of association schemes, and in particular the eigenspaces and eigenvalues of the Johnson scheme. Another is a combinatorial method we develop to compute (via traces) norm bounds for certain random matrices whose entries are highly dependent; we hope this method will be useful elsewhere.