TR26-100 | Bipartite Matching is in NC | Rohit Gurjar, Roshan Raj, Thomas Thierauf, Abhranil Chatterjee, Sumanta Ghosh

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