  Given a fixed graph $H$, a real number $p\in(0,1)$, and an infinite
Erd\H{o}s-R\'enyi graph $G\sim G(\infty,p)$, how many adjacency queries do we
have to make to find a copy of $H$ inside $G$ with probability $1/2$?
Determining this number $f(H,p)$ is a variant of the {\it subgraph query
problem} introduced by Ferber, Krivelevich, Sudakov, and Vieira. For every
graph $H$, we improve the trivial upper bound of $f(H,p) = O(p^{-d})$, where
$d$ is the degeneracy of $H$, by exhibiting an algorithm that finds a copy of
$H$ in time $o(p^{-d})$ as $p$ goes to $0$. Furthermore, we prove that there
are $2$-degenerate graphs which require $p^{-2+o(1)}$ queries, showing for the
first time that there exist graphs $H$ for which $f(H,p)$ does not grow like a
constant power of $p^{-1}$ as $p$ goes to $0$. Finally, we answer a question of
Feige, Gamarnik, Neeman, R\'acz, and Tetali by showing that for any $\delta <
2$, there exists $\alpha < 2$ such that one cannot find a clique of order
$\alpha \log_2 n$ in $G(n,1/2)$ in $n^\delta$ queries.

Combinatorics