Shotgun assembly of random regular graphs

Mossel and Ross (2019) introduce the shotgun assembly problem for random graphs: what radius $R$ ensures that the random graph $G$ can be uniquely recovered from its list of rooted $R$-neighborhoods, with high probability? Here we consider this question for random regular graphs of fixed degree $d\ge 3$. A result of Bollob'as (1982) implies efficient recovery at $R=(1+ϵ)\frac{1}{2}{\log }_{d-1}n$ with high probability – moreover, this recovery algorithm uses only a summary of the distances in each neighborhood. We show that using the full neighborhood structure gives a sharper bound $$R=\frac{\log n+\log \log n}{2\log (d-1)}+O(1),$$ which we prove is tight up to the $O(1)$ term. One consequence of our proof is that if $G,H$ are independent graphs where $G$ follows the random regular law, then with high probability the graphs are non-isomorphic; furthermore, this can be efficiently certified by testing the $R$-neighborhood list of $H$ against the $R$-neighborhood of a single adversarially chosen vertex of $G$.