Bipartite Perfect Matching is in quasi-NC

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

We show that the bipartite perfect matching problem is in quasi-NC${}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(lo{g}^{2}n)$ depth. Previousl…