We show that the bipartite matching problem is in NC. We extend the result to weighted bipartite matching and weighted linear matroid intersection. This in turn helps to show that the search versions of bipartite matching and linear matroid intersection are in NC as well. Additionally, we show that the computation of the noncommutative rank of a symbolic matrix is in NC. The techniques are based on a polynomial method, inspired from a construction of subspace design by Guruswami and Kopparty (Combinatorica 2016).

Added NC algorithms for weighted and search versions of linear matroid intersection.

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