Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-162 | 29th August 2026 14:59

Weighted Bipartite Matching is in $\text{Mod}_p \mathsf{L}$

RSS-Feed




TR26-162
Authors: Mingzi Xiao
Publication: 30th August 2026 18:05
Downloads: 80
Keywords: 


Abstract:

The recent paper \cite{chatterjee2026bipartite} showed that deciding whether a bipartite graph has a perfect matching can be reduced to deciding whether a determinant, whose value may be assigned to any sufficiently large field $\mathbb{F}$, equals to zero. In the second part of their work, \cite{chatterjee2026bipartite} also generalized the algebraic method and proposed an $\mathsf{NC}$ algorithm that computes the maximum \emph{weighted} perfect matching of bipartite graphs. However, the method they used relies on the positivity of non-zero sum of squares and does not generalize to finite fields. In this paper we further leverage their ideas and show that the algebraic method works in finite fields as well, therefore maximum weighted perfect bipartite matching is in $\text{Mod}_p \mathsf{L}$.



ISSN 1433-8092 | Imprint