An almost-efficient deterministic parallel algorithm for Bipartite Perfect Matching

Speaker:
Varun Ramanathan
Date:
Friday, 22 Jul 2022, 16:00 to 17:00
Venue:
A201
Abstract
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.