Tata Institute of Fundamental Research
An almost-efficient deterministic parallel algorithm for Bipartite Perfect Matching
STCS Student Seminar
Speaker:
Varun Ramanathan
Date:
Friday, 22 Jul 2022, 16:00 to 17:00
Venue:
A201
(Scan to add to calendar)
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.
| Speaker: | Varun Ramanathan |
| Date: | Friday, 22 Jul 2022, 16:00 to 17:00 |
| Venue: | A201 |
(Scan to add to calendar)
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.