Bipartite matching is in NC

Roshan Raj (Ohio State University) https://simons.berkeley.edu/talks/roshan-raj-ohio-state-university-2026-10-28 Derandomization 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. The techniques are based on a polynomial method, inspired from a construction of subspace design by Guruswami and Kopparty (Combinatorica 2016).