  In recent work, Mossel and Ross (2015) consider the shotgun assembly problem
for random graphs G: what radius R ensures that 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 (at least
three). A result of Bollobas (1982) implies efficient recovery at
$R=((1+\epsilon)\log n)/(2\log(d-1))$ 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 =
(\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; and 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.
