Bipartite Perfect Matching in Deterministic NC

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf.The post will try to explain three main things about the result. What is the result? Why is it important? And finally, how did the authors prove it? We will assume that the reader is an undergraduate student in CS (i.e., the reader knows basics of discrete mathematics, linear algebra, and algorithm design). What? The main result can be stated in just one line! Bipartite Perfect Matching can be solved in NC. Let's now understand what each of these terms means. Bipartite Perfect Matching. A bipartite graph has two disjoint sets of vertices, say \(L, R\), and any edge connects one vertex of \(L\) and one vertex of \(R\). A matching in a graph is a subset of edges such that no two edges have a vertex in common. A perfect matching is a matching in which each vertex of the graph appears…