Seeded Graph Matching via Large Neighborhood Statistics
  We study a well known noisy model of the graph isomorphism problem. In this
model, the goal is to perfectly recover the vertex correspondence between two
edge-correlated Erd\H{o}s-R\'{e}nyi random graphs, with an initial seed set of
correctly matched vertex pairs revealed as side information. For seeded
problems, our result provides a significant improvement over previously known
results. We show that it is possible to achieve the information-theoretic limit
of graph sparsity in time polynomial in the number of vertices $n$. Moreover,
we show the number of seeds needed for exact recovery in polynomial-time can be
as low as $n^{3\epsilon}$ in the sparse graph regime (with the average degree
smaller than $n^{\epsilon}$) and $\Omega(\log n)$ in the dense graph regime.
  Our results also shed light on the unseeded problem. In particular, we give
sub-exponential time algorithms for sparse models and an $n^{O(\log n)}$
algorithm for dense models for some parameters, including some that are not
covered by recent results of Barak et al.
