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).

Corrected the first part of the proof of Theorem 5.2

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).