Finding a planted clique by adaptive probing

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\sim G(n,1\mathrm{/}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(n^2 / k^2 + n)$adaptivequeriestotheadjacencymatrixof$G$ is likely to find the planted clique. On the other hand, when $k\ge (2+ϵ){\log }_{2}n$ there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making $q = O( (n^2 / k^2) \log^2 n

• n \log n)$adaptivequeries\mathrm{.}Fordetection,theadditive$n$ term is not necessary: the number of queries needed to detect the presence of a planted clique is $n^2\mathrm{/}{k}^2$ (up to logarithmic factors).