The main result (Thm 1.1) is that a maximum weight perfect matching in a bipartite graph, with polynomially bounded edge weights, can be found by a deterministic parallel algorithm with polynomially many processors in polylogarithmic time.
The point is that the parallel agorithm is deterministic rather than randomized, and that the number of processors is polynomial rather than quasi-polynomial. On the other hand, the result holds for bipartite graphs only rather than for general graphs.
The contents of the paper is said to be elementary, but it relies on several advanced notions and constructions, which are viewed as elementary: E.g., Section 1.2 starts saying ``[The proofs] only use the folded Wronskian criterion of linear independence of polynomials and the Hall's theorem (and its appropriate generalization for non-commutative rank).'' This section continues listing coding design problems that have inspired the current work, and then ends with the following two paragraphs:
Our starting point was the algorithm of [BCDZ26]. Via the equivalence with GZP(ell) codes and the associated generalized Hall Theorem, we showed that bipartite matching reduces to testing correctable erasure patterns for (m,n,1,b)-MR tensor codes. The algorithm in [BCDZ26] is supposed to work for all MR tensor codes, but assuming a matroid-theoretic conjecture. We observed that, even without the conjecture, it can be interpreted as an algorithm for computing the nc-rank of a special class of symbolic matrices. ... Our main insight was that both linear matroid intersection and noncommutative rank for arbitrary symbolic matrices reduce to this special class.The proofs presented in this paper are based on the polynomial method inspired from Guruswami-Kopparty [GK16] construction of subspace designs. They essentially boil down to the following amazing fact [GK16]: polynomials which have many disjoint high-multiplicity (or high foldedmultiplicity) zeroes are linearly independent. Our proof can also be written using subspace designs.
We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and the computation of the noncommutative rank of a symbolic matrix. In particular, this implies that the decision version of linear matroid intersection is in NC as well. The techniques are based on the polynomial method, inspired from a construction of subspace design by Guruswami and Kopparty (Combinatorica 2016).
See ECCC TR26-100.