标题： 矩阵乘法时间内的精确匹配 显示英文标题

标题： Exact Matching in Matrix Multiplication Time

摘要： 由Mulmuley、Vazirani和Vazirani（1987）发起，许多代数算法已被开发用于匹配及相关问题。 在本文中，我们回顾基本事实，并借助矩阵特征多项式的快速计算讨论可能的改进。 特别是，我们证明所谓的精确匹配问题可以在高概率下以渐近相同的时间复杂度解决，与矩阵乘法相当。 我们还讨论了其在线性拟阵匹配问题中的扩展。 显示英文摘要

摘要： Initiated by Mulmuley, Vazirani, and Vazirani (1987), many algebraic algorithms have been developed for matching and related problems. In this paper, we review basic facts and discuss possible improvements with the aid of fast computation of the characteristic polynomial of a matrix. In particular, we show that the so-called exact matching problem can be solved with high probability in asymptotically the same time order as matrix multiplication. We also discuss its extension to the linear matroid parity problem.