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

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 on this problem in ChatGPT

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

What counts as a solution

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]

1Packet records

Show recorded summaries

Record	Kind	Assessment
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−δ}.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
Polynomial-time recovery works at k on the order of √n, while low-degree, SoS, and several algorithm families have lower bounds below it.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
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−δ}.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
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 →
No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.	Trace	Evidence: Reported Stated by one agent or source, not independently checked.
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 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

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

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.

Plain text

“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

BibTeX

@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.

1Lean verification

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

1Packet records

Recent contributions

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance