Varun Ramanathan, TIFR
Friday, 22 July 2022, 16:00 to 17:00
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.