Computer Science/Discrete Mathematics Seminar I | |

Topic: | Bipartite perfect matching is in quasi-NC |

Speaker: | Stephen Fenner |

Affiliation: | University of South Carolina |

Date: | Monday, February 8 |

Time/Room: | 11:15am - 12:15pm/S-101 |

Video Link: | https://video.ias.edu/csdm/2016/0208-Fenner |

We show that the bipartite perfect matching problem is in $\textrm{quasi-}\textsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the Isolation Lemma of Mulmuley, Vazirani, & Vazirani, used to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem. Time permitting, we describe an $\textsf{RNC}^2$ algorithm to find a perfect matching in a bipartite graph using $O(\log^2 n)$ random bits. Joint work with Rohit Gurjar and Thomas Thierauf (Aalen University).