Exact Matching in Matrix Multiplication Time

Ryotaro Sato, Yutaro Yamaguchi · 2025

Read Exact Matching in Matrix Multiplication Time by Ryotaro Sato, Yutaro Yamaguchi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-04081.txt.

Description

Ryotaro Sato and Yutaro Yamaguchi present a math result from 2025 on the exact matching problem for graphs. Their work links the problem to fast matrix methods. The core tool is a pair of square matrices over a finite field, joined into a single matrix pencil.

Once one sum of the two matrices can be inverted, the full determinant can be rebuilt from one determinant, one inverse, and one characteristic polynomial. That step cuts the extra cost that a general method would add. Applied to a random check of the Tutte matrix, the trick gives a fast randomized test. It can tell, for all weights at once, whether a graph has a perfect matching of exact weight. The authors also extend the idea to matroid parity, path packing, and a shortest cycle task.

Catalog record

CREATORRyotaro Sato, Yutaro Yamaguchi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-04081

Browse the full library · About the Tower of Babel