Approximating the clique size of the graph Let $G=(V,E)$ be a graph. For a given $\rho \leq |V|$ and $\epsilon$ with $(0&lt;\epsilon&lt;1)$, is there any sublinear query algorithm known/possible to decide if the graph has a clique of size $\rho$, or all the cliques are of size at most $\rho(1-\epsilon)$. 

More precisely, for a given probability tolerance $\delta$ and error tolerance $\epsilon$, algorithm queries $f(\frac{1}{\epsilon}, \frac{1}{\delta}).o(n^2)$ many position of the corresponding adjacency matrix of the graph, and accept with probability at least $1-\delta$ if the graph has a clique of size $\rho$, or reject probability at least $1-\delta$ if all the cliques are of size at most $\rho(1-\epsilon).$

Thanks in advance.
It's not possible. The reason is that, to distinguish an $n$-vertex graph with no edges (clique size 1) from a graph with a single randomly-chosen edge (clique size 2) requires $\Theta(n^2)$ queries. So it's not possible to get sublinear queries for $\rho=2$ and $\epsilon&lt;\frac12$, but your question asks for a parameterization that remains sublinear for all $\rho$ and all $\epsilon&gt;0$.