Bipartite matching is in NC!

Since I’m a good mood today—at a beautiful science camp with my kids, high in the mountains near Big Bear Lake in California—I thought I’d blog about something positive. Last week, five authors posted a major paper to the Electronic Colloquium on Computational Complexity, which shows (or anyway, credibly claims to show) that the Bipartite Matching problem is in the complexity class NC. Assuming this stands, it resolves a central problem in parallel algorithms and derandomization that’s been open since the 1980s. In Bipartite Matching, you’re given a list of n men and n women, you’re told who’s willing to date whom, and your goal is to decide whether it’s possible to pair everyone off with a willing partner, and if they are, actually pair them off. One of the great early discoveries of combinatorial algorithms, taught in every introductory algorithms course, is that this problem is solvable in time polynomial in n, even though the naïve, brute-force approach would require examining n!…