[#P3130] Polynomial-time recovery of planted cliques below the square-root scale
Contents
Problem. Fix \(\delta>0\). Given a graph sampled by first drawing \(G(n,1/2)\) and then planting a uniformly random clique of size \(k=\lceil n^{1/2-\delta}\rceil\), is there a randomized polynomial-time algorithm that recovers the planted vertex set with probability tending to one?
Agent access
Work in ChatGPTThe agent reads this problem's research brief and asks you before it saves anything to TheoremDB.
Definitions and notation
1Context
Known frontier: Polynomial-time recovery works at k on the order of √n, while low-degree, sum-of-squares, and several algorithm families have lower bounds below it. Open boundary: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.
2Problem setup
Definition 1 (planted clique model). G(n,1/2) with every missing edge inside a random k-set added.
Definition 2 (recovery). Output the exact planted vertex set with probability 1−o(1).
Remark 1. Information-theoretic recovery is possible near logarithmic size, while known general polynomial-time methods require roughly the square-root scale. The packet fixes one constant δ to avoid mixing regimes.
3What counts as a solution
- For some fixed δ>0, give and prove a polynomial-time exact-recovery algorithm.
- Or prove polynomial-time recovery impossible under an explicit unconditional average-case model, which may require a new lower-bound framework.
1Status
Saved packet · August 1, 2026
Saved packet status (Current status and exact unresolved remainder). OPEN as checked on 2026-08-01. Strongest checked neighboring result: Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it. Exact unresolved remainder: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.[1][2]
1Packet records
Recent contributions
Saved work that is not yet in the reviewed packet, one entry per attempt.
Notes and companion material
Original intake status. OPEN as checked on 2026-08-01. Strongest checked neighboring result: Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it. Exact unresolved remainder: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.
- Equivalent-formulation queries: planted clique polynomial time below sqrt n current 2026; planted clique n one half minus delta recovery open
- Strongest checked neighboring result: Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it.
- Exact unresolved remainder: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.
How the 4 records connect
ProblemPolynomial-time recovery of planted cliques below the square-root scale
All 3 recorded relations between these records and the problem
2See also
- Multiplicative complexity of the six-bit threshold-at-least-three functiontheoretical computer science
- Polynomial determinization of two-way finite automatatheoretical computer science
- Logarithmic DFA separation of binary wordstheoretical computer science
Contribute to this problem
Cite this problem statement
Cite the original sources separately.
“Polynomial-time recovery of planted cliques below the square-root scale.” TheoremDB. P3130. Problem statement; statement text SHA-256 81f5ed0a6ec363dcd4533907249ba409827959f323ffc404a6fddb4020874d89. https://theoremdb.org/statement/?ref=P3130
@misc{theoremdb-problem-81f5ed0a6ec363dcd4533907249ba409827959f323ffc404a6fddb4020874d89,
title = {{Polynomial-time recovery of planted cliques below the square-root scale}},
howpublished = {TheoremDB},
note = {Problem statement; statement text SHA-256 81f5ed0a6ec363dcd4533907249ba409827959f323ffc404a6fddb4020874d89},
url = {https://theoremdb.org/statement/?ref=P3130}
}Plain text: Built Markdown snapshot
This problem includes 4 records joined by 3 typed links, sourced from arxiv.org[1], current as of August 1, 2026.
1References
- Packet source. R. Meka, A. Potechin, and A. Wigderson, Sum-of-squares lower bounds for planted clique, STOC 2015. main SoS lower bounds. ↗preprint · primary source · arXiv:1503.06447, checked 2026-08-01 · checked 2026-08-01Source use: original summary.Shows strong lower bounds for a major algorithmic hierarchy below the square-root regime.Also cited at R. Meka, A. Potechin, and A. Wigderson, Sum-of-squares lower bounds for planted clique, STOC 2015. main SoS lower bounds.Source used to assess the problem's recorded status.For Polynomial-time recovery of planted cliques below the square-root scale: This is the dated publication status for the canonical target Polynomial-time recovery of planted cliques below the square-root scale.Source named by the research packet.
- Reza Gheissari, Aukosh Jagannath, and Yiming Xu, “Finding Planted Cliques Using Gradient Descent”. SIAM Journal on Mathematics of Data Science 7(2) (2025), 643-669. DOI 10.1137/24M1680489. abstract and main results. ↗journal article · primary source · checked 2026-08-01Source use: original summary.States the continuing square-root algorithmic threshold and analyzes another broad method.Source used to assess the problem's recorded status.For Polynomial-time recovery of planted cliques below the square-root scale: States the continuing square-root algorithmic threshold and analyzes another broad method.
Original TheoremDB editorial statement and source synthesis; external works are used for citation only.
Discussion
Past commenters and subscribers receive notifications when someone comments.