[#P3130] Polynomial-time recovery of planted cliques below the square-root scale

A hidden clique inside a random graph. — A structural automaton diagram of the statement's mathematical objects.

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?

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

Current 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]

1Records

Record	Kind	Assessment
	Result	Supported
claim · Claim 1 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] Relevance to this problem This is the dated publication status for the canonical target Polynomial-time recovery of planted cliques below the square-root scale. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details The problem was checked as open on 2026-08-01. The strongest neighboring result found in the cited sources is: Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it. The exact unresolved remainder is: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}. A complete resolution must meet the following acceptance conditions: - 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. Open full record →
	Result	Supported
claim · Claim 2 Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it.^[1][2] Relevance to this problem Locates the present research frontier immediately below Polynomial-time recovery of planted cliques below the square-root scale. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1, Reference 2 Details Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it. This leaves the following boundary unresolved: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}. The distinction is retained here so a restricted theorem, finite computation, or neighboring case is not presented as a solution of the full target. Related: Claim 1 Open full record →
	Trace	Supported
attempt · Route 1 The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked 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. Unresolved remainder: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.^[1][2] Relevance to this problem Documents why Polynomial-time recovery of planted cliques below the square-root scale was treated as a distinct open target on 2026-08-01. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2 What happened The audit ran on 2026-08-01 across the cited primary literature and problem collections, Crossref, arXiv, and stable publisher records, TheoremDB published, prospecting, packet, formal, and retired corpus. It checked the exact statement, its named or normalized variants, recent status evidence, and the controlled TheoremDB corpus. Queries included: - planted clique polynomial time below sqrt n current 2026 - planted clique n one half minus delta recovery open The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked 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. Unresolved remainder: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}. Related: Claim 1 Open full record →
	Trace	Reported
attempt · Route 2 No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}. Relevance to this problem Turns the remaining uncertainty in Polynomial-time recovery of planted cliques below the square-root scale into a checkable research target. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded What happened Research should address this boundary directly: No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}. A claimed resolution should satisfy every item below and preserve the statement's exact quantifiers and normalizations: - 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. Related: Claim 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

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 connectTyped relations and evidence flow

ProblemPolynomial-time recovery of planted cliques below the square-root scale

Claim 1Current status and exact unresolved remainderin this packetSupported
Route 1Dated source and duplicate auditchecksSupported
Claim 2Strongest checked neighboring resultinformsSupported
Route 2Work at the unresolved boundaryaddressesReported

2See also

Is VP equal to VNP?theoretical computer science
Is there a truly subcubic algorithm for weighted APSP?theoretical computer science
Strong Exponential Time Hypothesistheoretical computer science

How to cite

TheoremDB contributors, “Polynomial-time recovery of planted cliques below the square-root scale,” TheoremDB research memory, snapshot of August 1, 2026. https://theoremdb.org/statements/planted-clique-below-square-root

This page as plain text: planted-clique-below-square-root.md

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.

[#P3130] Polynomial-time recovery of planted cliques below the square-root scale

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Records

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance