  We consider the problem of finding a large clique in an Erd\H{o}s--R\'enyi
random graph where we are allowed unbounded computational time but can only
query a limited number of edges. Recall that the largest clique in $G \sim
G(n,1/2)$ has size roughly $2\log_{2} n$. Let $\alpha_{\star}(\delta,\ell)$ be
the supremum over $\alpha$ such that there exists an algorithm that makes
$n^{\delta}$ queries in total to the adjacency matrix of $G$, in a constant
$\ell$ number of rounds, and outputs a clique of size $\alpha \log_{2} n$ with
high probability. We give improved upper bounds on
$\alpha_{\star}(\delta,\ell)$ for every $\delta \in [1,2)$ and $\ell \geq 3$.
We also study analogous questions for finding subgraphs with density at least
$\eta$ for a given $\eta$, and prove corresponding impossibility results.
