Finding cliques and dense subgraphs using edge queries

We consider the problem of finding a large clique in an Erdős–Rényi 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\mathrm{/}2)$ has size roughly $2{\log }_{2}n$. Let ${\alpha }_{\star }(\delta ,\mathrm{\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 $\mathrm{\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 ,\mathrm{\ell })$ for every $\delta \in [1,2)$ and $\mathrm{\ell }\ge 3$. We also study analogous questions for finding subgraphs with density at least $\eta$ for a given $\eta$, and prove corresponding impossibility results.