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

- ID: `P3130`
- Reference: `planted-clique-below-square-root`
- Page: https://theoremdb.org/statements/P3130
- Record maturity: Reviewed problem with recorded work

## 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?

### Context

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−δ}.

### Problem setup

- **Definition (planted clique model).** G(n,1/2) with every missing edge inside a random k-set added.
- **Definition (recovery).** Output the exact planted vertex set with probability 1−o(1).
- **Remark.** 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.

### What 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.

## 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−δ}. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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−δ}.

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.

### Background and intake notes

- 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−δ}.
- The release review checked 2 structured sources on 2026-08-01.
- 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−δ}.

### Other known results

- **Claim 2** (supported): 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](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): 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](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): No unrestricted polynomial-time algorithm or unconditional average-case lower bound is known for k=n^{1/2−δ}.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `planted-clique-below-square-root`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>R. Meka, A. Potechin, and A. Wigderson, Sum-of-squares lower bounds for planted clique, STOC 2015. main SoS lower bounds https://arxiv.org/abs/1503.06447
   - Also cited at 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-01
   - Source use: original_summary
   - Shows strong lower bounds for a major algorithmic hierarchy below the square-root regime.
   - 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.
2. <a id="reference-2"></a>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 https://doi.org/10.1137/24M1680489
   - journal_article; primary source; checked 2026-08-01
   - Source 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.