  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/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)$ adaptive queries to the adjacency matrix of $G$ is likely to
find the planted clique. On the other hand, when $k \geq (2+\epsilon) \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)$ 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 $n^2 / k^2$ (up to logarithmic factors).
