Planted clique at k = n^(1/2−ε): hardness beyond low-degree polynomials and sum-of-squares
An unusually precise open question: the threshold is known on the algorithmic side and matched by several restricted-model lower bounds, but no reduction from a standard assumption exists, and such reductions are widely thought to need new ideas (average-case-to-worst-case barriers). Application value is modest, mostly guiding which statistical tasks are tractable. Leverage is relatively high because dozens of average-case hardness results use it as a base assumption.
The problem
A hidden clique in a random network is easy to spot above a size threshold and seems hard below it.
- 1Plant a clique in a random network
- 2Large cliques: simple methods find them
- 3Just below √n: no method known
- 4Hardness only shown for limited methods
- 5Open: derive hardness from a standard assumption
The model. Sample a graph from (each pair is an edge independently with probability ) and plant a clique on uniformly random vertices. means distinguishing this from a plain . means finding the clique.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Computational complexity theoryTheory · host
- Then
- Planted clique at k = n^(1/2−ε): hardness beyond low-degree polynomials and sum-of-squaresThe problem
State of the art
Algorithmic upper bounds. Alon, Krivelevich and Sudakov (Random Structures & Algorithms 1998) found cliques of size by spectral methods; Feige and Krauthgamer, and Dekel, Gurel-Gurevich and Peres (2014) gave variants. Nothing polynomial-time is known below .
Realistic applications
A proof of hardness from a standard assumption would put a large literature of statistical-computational gaps (sparse PCA, community detection, tensor problems, certain cryptographic primitives based on planted structures) on firm ground; a polynomial-time algorithm below would overturn the heuristic picture that low-degree hardness predicts computational hardness.
What counts as solved
(a) A reduction from a standard problem (for example worst-case lattice or hidden-structure assumptions, or a well-studied average-case problem) establishing hardness of detection at for every ; or (b) a polynomial-time algorithm for some . A proof of hardness against a significantly broader class than low-degree and SoS (for example all constant-depth algorithms or all local algorithms) would be partial progress.
How it gets verified
Expert reviewOnly expert review of the argument is possible today.
The target is a reduction from a standard problem showing hardness of planted-clique detection at k = n^(1/2-eps), or a polynomial-time algorithm. This is average-case complexity, with no Mathlib framework, so experts review the reduction. Hardness against low-degree and sum-of-squares algorithms is already known, and a result against a broader class would be partial progress.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Pure proof/reduction work; numerical experiments only probe small cases.
Bottlenecks
ranked by votes- #1TheoryNo worst-case or standard-assumption reduction
Average-case-to-worst-case reductions for natural planted problems face the known barriers of Bogdanov–Trevisan type; planted clique is not even known to be hard from NP-hardness.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Jun 12, 2025Low-degree surveysource
Wein surveys low-degree lower bounds, including the k ≈ √n detection threshold for planted clique, and lists open questions.
- Jun 19, 2018Reductions from planted cliquesource
Brennan, Bresler and Huleihel derived computational lower bounds for many planted-structure problems from planted clique.
- Apr 11, 2016Nearly tight SoS lower boundsource
Barak et al. proved that degree-d sum-of-squares fails to refute the absence of a clique of size n^(1/2 − c√(d/log n)), which is n^(1/2−o(1)) for d = o(log n).