Abstract: Random graph matching refers to recovering the underlying vertex correspondence between

two Erd\H{o}s-R\'{e}nyi graphs with correlated edges. This can be viewed as an average-case and noisy

version of the graph isomorphism problem. The maximum likelihood estimator is equivalent to the 

intractable quadratic assignment problem. 

For seeded problems, where an initial seed set of correctly matched vertex pairs is revealed as side

information, our result provides a dramatic 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^{\epsilon}$ in the sparse graph regime with the average degree

smaller than $n^{\epsilon}$) and $\Omega(\log n)$ in the dense graph regime. 

For unseeded problems, we develop a nearly linear-time algorithm which perfectly recovers the

underlying true vertex correspondence, provided that the two observed graphs differ by at most

$epsilon=O(1/log^2(n) )$ fraction of edges in the sparse graph regime and $espilon=O( 1/log^{2/3}(n) )$ 

fraction of edges in the dense graph regime. The best-known result before this work achieves $\epsilon=

O(1)$ with an $n^{O(\log n)}$-time algorithm.

Bio: Jiaming Xu is an Assistant Professor in the academic area of decision sciences in the Fuqua School

of Business at Duke University.  He received a B.E. from Tsinghua University in Beijing in 2009, an M.S.

from UT Austin in 2011, and a Ph.D. from University of Illinois at Urbana-Champaign in 2014, all in

Electrical and Computer Engineering. He joined the Krannert School of Management at Purdue University

as an Assistant Professor in 2016. Before that, he was a Research Fellow with the Simons Institute for the

Theory of Computing, University of California, Berkeley, and a Postdoctoral Fellow with the Statistics

Department, The Wharton School, University of Pennsylvania. His research interests include data science,

high-dimensional statistical inference, information theory, convex and non-convex optimization, queueing

theory, and game theory. Dr. Xu received a Simons-Berkeley Fellowship in 2016 and the Outstanding

Graduate Student Award conferred by the UIUC College of Engineering in 2014.