(Nearly) Efficient Algorithms for the Graph Matching Problem on
  Correlated Random Graphs
  We give a quasipolynomial time algorithm for the graph matching problem (also
known as noisy or robust graph isomorphism) on correlated random graphs.
Specifically, for every $\gamma>0$, we give a $n^{O(\log n)}$ time algorithm
that given a pair of $\gamma$-correlated $G(n,p)$ graphs $G_0,G_1$ with average
degree between $n^{\varepsilon}$ and $n^{1/153}$ for $\varepsilon = o(1)$,
recovers the "ground truth" permutation $\pi\in S_n$ that matches the vertices
of $G_0$ to the vertices of $G_n$ in the way that minimizes the number of
mismatched edges. We also give a recovery algorithm for a denser regime, and a
polynomial-time algorithm for distinguishing between correlated and
uncorrelated graphs.
  Prior work showed that recovery is information-theoretically possible in this
model as long the average degree was at least $\log n$, but sub-exponential
time algorithms were only known in the dense case (i.e., for $p > n^{-o(1)}$).
Moreover, "Percolation Graph Matching", which is the most common heuristic for
this problem, has been shown to require knowledge of $n^{\Omega(1)}$ "seeds"
(i.e., input/output pairs of the permutation $\pi$) to succeed in this regime.
In contrast our algorithms require no seed and succeed for $p$ which is as low
as $n^{o(1)-1}$.
