Finding paths in sparse random graphs requires many queries

We discuss a new algorithmic type of problem in random graphs studying the minimum number of queries one has to ask about adjacency between pairs of vertices of a random graph G ∼ G(n, p) in order to find a subgraph which possesses some target property with high probability. In this paper we focus on finding long paths in G ∼ G(n, p) when p = 1+εn for some fixed constant ε> 0. This random graph is known to have typically linearly long paths. To have ` edges with high probability in G ∼ G(n, p) one clearly needs to query at least