In this paper we present a pseudo-deterministic RN C algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses pol y ( n ) processors, pol y ( log n ) depth, pol y ( log n ) random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That is, it returns the same matching for almost all random seeds.

Our work improves upon different aspects of prior work. The celebrated works of Karp, Uval, Wigderson and Mulmuley, Vazirani, Vazirani which find perfect matchings in RN C produce different matchings on different executions. The recent work of Fenner, Gurjar, and Thierauf shows a deterministic parallel algorithm for bipartite perfect matching but requires 2 pol y ( log n ) (quasi polynomially many) processors, proving that bipartite matching is in quasi- N C . Our algorithm is the first algorithm to return unique perfect matchings with only polynomially many processors.

As an immediate consequence we also find a pseudo-deterministic RN C algorithm for depth first search (DFS).