Polynomial-time detection below the planted-clique square-root threshold
Fix $0 < \varepsilon < 1/2$ and put $k_n = \lfloor n^{1/2-\varepsilon} \rfloor$. Let $P_{0,n}$ be the law of the Erdős–Rényi graph $G(n, 1/2)$ on $n$ labelled vertices, and let $P_{1,n}$ be the law of the graph obtained by sampling from $P_{0,n}$, choosing an independent uniformly random set of $k_n$ vertices and adding all missing edges inside it. A test is a randomized algorithm $A$ that outputs $0$ or $1$ from the observed graph $G$, in time polynomial in the size of its adjacency matrix; probabilities below include the algorithm's internal randomness.
Alon, Krivelevich and Sudakov gave a polynomial-time algorithm that finds the planted clique with high probability when $k > c\sqrt{n}$, for any fixed $c > 0$. Barak, Hopkins, Kelner, Kothari, Moitra and Potechin proved that, with high probability on $G(n, 1/2)$, the degree-$d$ sum-of-squares relaxation of the clique problem has value at least $n^{1/2 - c(d/\log n)^{1/2}}$ for some constant $c > 0$. Brennan, Bresler and Huleihel use the conjectured hardness below the square-root threshold as the hypothesis of average-case reductions to other detection problems with planted sparse structure.
Problem. Does every randomized polynomial-time algorithm $A$ satisfy $$\liminf_{n \to \infty} \Bigl[ P_{0,n}\{A(G) = 1\} + P_{1,n}\{A(G) = 0\} \Bigr] \ge 1,$$ for every $\varepsilon \in (0, 1/2)$, with the algorithm and $\varepsilon$ fixed before taking the limit? That is, can no such algorithm achieve a nonvanishing advantage over guessing? Advantages tending to zero are allowed, and the algorithm need not identify the planted vertices.
Source: Jerrum (1992) and Kučera (1995) introduced the planted clique problem; the detection conjecture is Brennan, Bresler and Huleihel (2018), Conjecture 1 (PC Conjecture), and Huleihel, Mazumdar and Pal (2024), Conjecture 4, for sequences of algorithms and all k_n with lim sup log k_n / log n < 1/2. Stated for edge density 1/2 and k_n = ⌊n^{1/2−ε}⌋ by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- ST — Statistics Theory
- Secondary
- CO, PR
- Keywords
- AIM Open Applied Problems, computational lower bounds, planted cliques, random graphs
References
@article{jerrum1992,
author = {Jerrum, Mark},
title = {Large cliques elude the {M}etropolis process},
journal = {Random Structures Algorithms},
volume = {3},
number = {4},
year = {1992},
pages = {347--359},
doi = {10.1002/rsa.3240030402},
}
@article{kucera1995,
author = {Ku{\v{c}}era, Lud{\v{e}}k},
title = {Expected complexity of graph partitioning problems},
journal = {Discrete Appl. Math.},
volume = {57},
number = {2-3},
year = {1995},
pages = {193--212},
doi = {10.1016/0166-218X(94)00103-K},
}
@inproceedings{brennan2018,
author = {Brennan, Matthew and Bresler, Guy and Huleihel, Wasim},
title = {Reducibility and computational lower bounds for problems with planted sparse structure},
booktitle = {Proceedings of the 31st Conference on Learning Theory},
series = {Proceedings of Machine Learning Research},
volume = {75},
year = {2018},
pages = {48--166},
eprint = {1806.07508},
archivePrefix = {arXiv},
}
@article{huleihel2024,
author = {Huleihel, Wasim and Mazumdar, Arya and Pal, Soumyabrata},
title = {Random subgraph detection using queries},
journal = {J. Mach. Learn. Res.},
volume = {25},
number = {126},
year = {2024},
pages = {1--25},
url = {http://jmlr.org/papers/v25/22-0395.html},
}
@article{alon1998,
author = {Alon, Noga and Krivelevich, Michael and Sudakov, Benny},
title = {Finding a large hidden clique in a random graph},
journal = {Random Structures Algorithms},
volume = {13},
number = {3-4},
year = {1998},
pages = {457--466},
doi = {10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W},
}
@article{barak2019,
author = {Barak, Boaz and Hopkins, Samuel B. and Kelner, Jonathan and Kothari, Pravesh K. and Moitra, Ankur and Potechin, Aaron},
title = {A nearly tight sum-of-squares lower bound for the planted clique problem},
journal = {SIAM J. Comput.},
volume = {48},
number = {2},
year = {2019},
pages = {687--735},
doi = {10.1137/17M1138236},
eprint = {1604.03084},
archivePrefix = {arXiv},
}
@misc{aim-planted-clique,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Polynomial-time detection below the planted-clique square-root threshold}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/292-planted-clique.md},
note = {Entry 292 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00548, "Polynomial-time detection below the planted-clique square-root threshold", clopen.solutions.