Bipartite Perfect Matching is in quasi-NC

Stephen Fenner, Rohit Gurjar, Thomas Thierauf

The perfect matching problem has a randomized NC-algorithm based on the Isolation Lemma of Mulmuley, Vazirani and Vazirani. We give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic Quasi-NC-algorithm for the bipartite perfect matching problem.

The outline presented here emphasizes a geometric point of view. We think that this will be useful also for the perfect matching problem in general graphs.