Bipartite perfect matching is in quasi-NC
Stephen Fenner, Rohit Gurjar, Thomas Thierauf · 2016
We show that the bipartite perfect matching problem is in quasi- NC2. That is, it has uniform circuits of quasi-polynomial size nO(logn), and O(log2 n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.