In this talk, I will explain the Isolation lemma introduced by Mulmuley, Vazirani, Vazirani in [MVV87] and use it to get an upper bound on the parallel complexity of bipartite perfect matching. The Isolation lemma has also been instrumental in the design of randomized algorithms and has contributed to several significant complexity upper bounds.
I will present a parallel algorithm for bipartite matching achieved through the derandomization of the isolation lemma. This result demonstrates that the bipartite perfect matching problem lies in $Quasi-NC^2$.
The talk will be based on the paper "Bipartite Perfect Matching is in quasi-NC" by Fenner, Gurjar and Thierauf.
