  We propose a simple and efficient local algorithm for graph isomorphism which
succeeds for a large class of sparse graphs. This algorithm produces a
low-depth canonical labeling, which is a labeling of the vertices of the graph
that identifies its isomorphism class using vertices' local neighborhoods.
  Prior work by Czajka and Pandurangan showed that the degree profile of a
vertex (i.e., the sorted list of the degrees of its neighbors) gives a
canonical labeling with high probability when $n p_n = \omega( \log^{4}(n) /
\log \log n )$ (and $p_{n} \leq 1/2$); subsequently, Mossel and Ross showed
that the same holds when $n p_n = \omega( \log^{2}(n) )$. We first show that
their analysis essentially cannot be improved: we prove that when $n p_n = o(
\log^{2}(n) / (\log \log n)^{3} )$, with high probability there exist distinct
vertices with isomorphic $2$-neighborhoods. Our first main result is a positive
counterpart to this, showing that $3$-neighborhoods give a canonical labeling
when $n p_n \geq (1+\delta) \log n$ (and $p_n \leq 1/2$); this improves a
recent result of Ding, Ma, Wu, and Xu, completing the picture above the
connectivity threshold.
  Our second main result is a smoothed analysis of graph isomorphism, showing
that for a large class of deterministic graphs, a small random perturbation
ensures that $3$-neighborhoods give a canonical labeling with high probability.
While the worst-case complexity of graph isomorphism is still unknown, this
shows that graph isomorphism has polynomial smoothed complexity.
