Exact Matching in Matrix Multiplication Time

由 Mulmuley、Vazirani 和 Vazirani（1987 年）发起，许多用于匹配及相关问题的代数算法相继被提出。本文中，我们回顾了一些基本结论，并借助矩阵特征多项式的快速计算，探讨了可能的改进方法。特别是，我们表明，所谓的精确匹配问题可以在渐近相同于矩阵乘法的时间复杂度下，以高概率得到解决。我们还讨论了该方法在拟阵匹配问题中的推广形式。

论文试图解决匹配问题（如精确匹配问题）以及线性拟阵奇偶性问题，目标是通过快速计算矩阵的特征多项式，设计出更高效的代数算法。这是一个在理论计算机科学和算法设计中长期存在的问题。

论文的关键思路是利用矩阵特征多项式的快速计算技术，将精确匹配问题的求解时间复杂度降低到与矩阵乘法相近的水平，并通过概率方法实现高效求解。这一思路结合了代数算法与随机化技术，相比已有方法，提供了更优的时间复杂度保证。

1. 提出了一种基于特征多项式计算的高效算法，解决精确匹配问题。 2. 将精确匹配问题的复杂度降低到接近矩阵乘法的时间复杂度。 3. 扩展了方法至线性拟阵奇偶性问题，展示了其广泛适用性。 4. 通过理论分析而非实验验证，展示了算法的高概率正确性。

1. Karp, R. M., Vazirani, U. V., & Vazirani, V. V. (1986). An optimal algorithm for on-line bipartite matching. 2. Lovász, L. (1980). On the structure of factorizable graphs. 3. Sankowski, P. (2007). Faster dynamic matchings and vertex fail connectivity. 4. Cheung, Y. T., Gong, L., & Ramachandran, V. (2012). Algebraic algorithms for matching and matroid problems. 5. Chien, S. (2004). A determinant-based algorithm for counting perfect matchings in a general graph.