Title: Bipartite Perfect Matching is in Quasi-NC
| Speaker: | Rian Neogi |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: Mulmuley, Vazirani, and Vazirani gave a randomized parallel algorithm for checking whether a perfect matching exists in a graph. In doing so, they came up with the infamous isolation lemma, which found several uses in other areas of computer science. The isolation lemma is inherently randomized, and it has been a long-standing open problem to derandomize the lemma. In this talk, I will go over the breakthrough work of Fenner, Gurjar, and Thierauf where they almost completely derandomize the isolation lemma in the special case when applied to the bipartite perfect matching problem. In doing so, they give a deterministic parallel algorithm for perfect matching that uses a quasi-polynomial number of processors.