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 @math be a random graph on @math vertices with a planted clique of size @math . We show that no algorithm that makes at most @math adaptive queries to the adjacency matrix of @math is likely to find the planted clique. On the other hand, when @math there exists a simple algorithm (with unbounded computational power) that finds the planted clique with high probability by making @math adaptive queries. For detection, the additive @math term is not necessary: the number of queries needed to detect the presence of a planted clique is @math (up to logarithmic factors).
Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an @math vertex graph, and need to output a clique. We show that if the input graph is drawn at random from @math (and hence is likely to have a clique of size roughly @math ), then for every @math and constant @math , there is an @math (that may depend on @math and @math ) such that no algorithm that makes @math probes in @math rounds is likely (over the choice of the random graph) to output a clique of size larger than @math .