IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Bipartite Perfect Matching is in quasi-NC

  • Feb. 5, 2016
  • 2:30 p.m.
  • LeConte 312

Abstract

We show that the bipartite perfect matching problem is in 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, which was 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).

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC