Exact Matching in Matrix Multiplication Time
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911093837791232 |
|---|---|
| author | Sato, Ryotaro Yamaguchi, Yutaro |
| author_facet | Sato, Ryotaro Yamaguchi, Yutaro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_04081 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exact Matching in Matrix Multiplication Time Sato, Ryotaro Yamaguchi, Yutaro Data Structures and Algorithms Symbolic Computation Combinatorics 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. |
| title | Exact Matching in Matrix Multiplication Time |
| topic | Data Structures and Algorithms Symbolic Computation Combinatorics |
| url | https://arxiv.org/abs/2508.04081 |