The Planted Clique Conjecture

Planted clique conjecture: let \(G \sim G(n, 1/2)\) with a \(k\)-clique planted on a random \(k\)-subset, where \(k = o(\sqrt{n})\). Then no polynomial-time algorithm recovers the planted clique with non-negligible probability. (Above \(\sqrt{n}\), spectral methods succeed; the conjecture is the \(o(\sqrt{n})\) regime.)

Planted problems became the testbed of average-case complexity in the 2000s–2010s: Jerrum (1992) suggested the planted clique as a hard-on-average problem, and it now anchors reductions for sparse PCA, community detection and cryptographic candidates. Spectral methods and degree-\(O(\log n)\) sum-of-squares hierarchies recover cliques of size \(\gg \sqrt{n}\), while below \(\sqrt{n}\) every known polynomial-time method fails — matching the conjectured threshold. Low-degree lower bounds (Hopkins–Steurer and successors) formalise the failure without proving hardness.