Finding cliques using few probes

Abstract

Consider algorithms with unbounded computation time that probe the entries of the adjacency matrix of an $n$ vertex graph, and need to output a clique. We show that if the input graph is drawn at random from $G_{n,\frac{1}{2}}$ (and hence is likely to have a clique of size roughly $2\log n$), then for every $\hat{I}´<2$ and constant $\ell$, there is an $\hat{I}\pm <2$ (that may depend on $\hat{I}´$ and $\ell$) such that no algorithm that makes $n^{\hat{I}}´$ probes in $\ell$ rounds is likely (over the choice of the random graph) to output a clique of size larger than $\hat{I}\pm \log n$.

15 pages