On the subgraph query problem

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(\mathrm{\infty },p)$, how many adjacency queries do we have to make to find a copy of $H$ inside $G$ with probability $1\mathrm{/}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$,thereexists$\alpha < 2$suchthatonecannotfindacliqueoforder$\alpha \log_2 n$in$G(n,1/2)$in$n^\delta$ queries.