An almost-efficient deterministic parallel algorithm for Bipartite Perfect Matching



Friday, 22 July 2022, 16:00 to 17:00


  • A201

We will try to understand the paper "Bipartite Perfect Matching is in quasi-NC" by Fenner, Gurjar and Thierauf (2016). They achieved an almost complete derandomization of the Isolation Lemma (Mulmuley, Vazirani, Vazirani) for perfect matchings in bipartite graphs and thus the result stated in the title. There are no prerequisites for the talk; familiarity with linear programming would be helpful.