| Description |
In this talk we will see an efficient parallel algorithm for the Bipartite Perfect Matching problem (BPM) due to Fenner, Gurjar and Thierauf. The Perfect Matching problem (PM) is to decide whether a given graph has a perfect matching. Edmonds gave a polynomial time algorithm for the Perfect Matching problem in 1965. However its parallel complexity is still not completely resolved as of today. Fenner et al. showed that BPM can be solved using uniform circuits of quasi-polynomial size n^O(log n), and O(log^2 n) depth where n is the number of vertices in the input graph. Previously only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. The result of Ferner et al. is essentially a derandomization of the Isolation lemma based randomized algorithm due to Mulmuley, Vazirani and Vazirani. We will also see an elegant proof of the Isolation Lemma due to Noam Tashma.
|