Reconstructing random graphs from distance queries

We estimate the minimum number of distance queries that is sufficient to reconstruct the binomial random graph $G(n,p)$ with constant diameter with high probability. We get a tight (up to a constant factor) answer for all p>n⁻¹⁺ᵒ⁽¹⁾ outside "threshold windows" around n-k/(k+1)+o(1), k>0: with high probability the query complexity equals Θ(n⁴⁻ᵈp²⁻ᵈ), where d is the diameter of the random graph. This demonstrates the following non-monotone behaviour: the query complexity jumps down at moments when the diameter gets larger; yet, between these moments the query complexity grows. We also show that there exists a non-adaptive algorithm that reconstructs the random graph with O(n⁴⁻ᵈp²⁻ᵈln n) distance queries with high probability, and this is best possible.