Math Conjectures

Planted Clique Conjecture

OPENMajorConjectureProposed 1992–1998 · Standard version

Canonical statement

For every fixed ε∈(0,1/2)\varepsilon\in(0,1/2), there is no randomized polynomial-time algorithm AA such that, for all sufficiently large nn, the following hypotheses are distinguished:
H0:each edge of a graph on [n] is independently present with probability 12; H_0:\text{each edge of a graph on }[n]\text{ is independently present with probability }\tfrac12;
H1:sample as under H0, choose uniformly a k=⌊n1/2−ε⌋-vertex set, and add all its missing edges. H_1:\text{sample as under }H_0,\text{ choose uniformly a } k=\lfloor n^{1/2-\varepsilon}\rfloor\text{-vertex set, and add all its missing edges}.
More precisely, no such AA satisfies Pr⁡[A(G)=i∣Hi]≥2/3\Pr[A(G)=i\mid H_i]\geq2/3 for both i∈{0,1}i\in\{0,1\}.
View source LaTeX
For every fixed \(\varepsilon\in(0,1/2)\), there is no
randomized polynomial-time algorithm \(A\) such that, for all
sufficiently large \(n\), the following hypotheses are distinguished:
\[
  H_0:\text{each edge of a graph on }[n]\text{ is independently present
  with probability }\tfrac12;
\]
\[
  H_1:\text{sample as under }H_0,\text{ choose uniformly a }
  k=\lfloor n^{1/2-\varepsilon}\rfloor\text{-vertex set, and add all
  its missing edges}.
\]
More precisely, no such \(A\) satisfies
\(\Pr[A(G)=i\mid H_i]\geq2/3\) for both \(i\in\{0,1\}\).
TCS-022:[Jerrum1992Clique][AlonKrivelevichSudakov1998][BrennanBreslerHuleihel2018]
Theoretical computer scienceProbability theory

Notes

The planted clique conjecture concerns distinguishing an Erdős–Rényi random graph G(n,12)G(n,\tfrac12) from the same model after all edges inside a uniformly chosen set of k=⌊n1/2−ε⌋k=\lfloor n^{1/2-\varepsilon}\rfloor vertices have been added. It asserts that for every fixed ε∈(0,1/2)\varepsilon\in(0,1/2) no randomized polynomial-time algorithm identifies the correct hypothesis with probability at least 2/32/3 in both cases. Its origins span 1992–1998: Jerrum showed that the Metropolis process fails to find large hidden cliques [Jerrum1992Clique], and Alon, Krivelevich and Sudakov gave the now-standard planted formulation together with an efficient algorithm for large cliques [AlonKrivelevichSudakov1998].

The known landscape frames the conjecture precisely. Exhaustive search succeeds at the information-theoretic logarithmic scale of kk, but in super-polynomial time, while spectral and related polynomial-time methods succeed once k≳nk\gtrsim\sqrt n [AlonKrivelevichSudakov1998]. In the gap between these regimes no efficient algorithm is known, and the conjectured hardness there has become a widely used assumption, transferred by reductions to other planted problems [BrennanBreslerHuleihel2018].

The conjecture remains open: proving it requires average-case lower bounds beyond current techniques, while refuting it needs a polynomial-time distinguisher below the n\sqrt n threshold.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.