# Finding a planted clique by adaptive probing

arXiv: https://arxiv.org/abs/1903.12050 · HTML: https://mlsanity.com/paper/1903.12050/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Mar 2019.

## Built on by (most cited first, 6 of 6)

- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [Harnessing Multiple Correlated Networks for Exact Community Recovery](https://mlsanity.com/paper/2412.02796/) (2024)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Low-degree phase transitions for detecting a planted clique in sublinear time](https://mlsanity.com/paper/2402.05451/) (2024)
- [Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods](https://mlsanity.com/paper/2510.16609/) (2025)

## Abstract (arXiv)

We consider a variant of the planted clique problem where we are allowed unbounded computational time but can only investigate a small part of the graph by adaptive edge queries. We determine (up to logarithmic factors) the number of queries necessary both for detecting the presence of a planted clique and for finding the planted clique. Specifically, let G ~ G(n,1/2,k) be a random graph on n vertices with a planted clique of size k. We show that no algorithm that makes at most q = o(n2 / k2 + n) adaptive queries to the adjacency matrix of G is likely to find the planted clique. On the other hand, when k ≥ (2+ε) log2 n there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making q = O( (n2 / k2) log2 n + n log n) adaptive queries. For detection, the additive n term is not necessary: the number of queries needed to detect the presence of a planted clique is n2 / k2 (up to logarithmic factors).