论文标题
多项式时间迭代算法，用于匹配高斯矩阵与非变化相关的算法
A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
论文作者
论文摘要
在两个相关的Erdős-rényi图中匹配顶点的问题的动机，我们研究了与两个相关的高斯Wigner矩阵匹配的问题。我们提出了一种迭代匹配算法，只要两个高斯矩阵之间的相关性不会消失，该算法就在多项式时间内成功。我们的结果是第一个多项式时间算法，该算法在任意的常数为小常数时求解图形匹配的问题类型。
Motivated by the problem of matching vertices in two correlated Erdős-Rényi graphs, we study the problem of matching two correlated Gaussian Wigner matrices. We propose an iterative matching algorithm, which succeeds in polynomial time as long as the correlation between the two Gaussian matrices does not vanish. Our result is the first polynomial time algorithm that solves a graph matching type of problem when the correlation is an arbitrarily small constant.
