We present a pseudo-deterministic NC algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $\poly(n)$ processors, $\poly({\log n})$ depth, $\poly(\log n)$ random bits, and outputs for each bipartite input graph a {\bf unique} perfect matching with high probability. That is, on the same graph it returns the same matching for almost all choices of randomness. As an immediate consequence we also find a pseudo-deterministic NC algorithm for constructing a depth first search (DFS) tree. We introduce a method for computing the union of all min-weight perfect matchings of a weighted graph in RNC and a novel set of weight assignments which in combination enable isolating a unique matching in a graph.

We then show a way to use pseudo-deterministic algorithms to reduce the number of random bits used by general randomized algorithms. The main idea is that random bits can be {\it reused} by successive invocations of pseudo-deterministic randomized algorithms. We use the technique to show an RNC algorithm for constructing a depth first search (DFS) tree using only $O(\log^2 n)$ bits whereas the previous best randomized algorithm used $O(\log^7 n)$, and a new sequential randomized algorithm for the set-maxima problem which uses fewer random bits than the previous state of the art.

Furthermore, we prove that resolving the decision question $NC = RNC$, would imply an NC algorithm for finding a bipartite perfect matching and finding a DFS tree in NC. This is not implied by previous randomized NC search algorithms for finding bipartite perfect matching, but is implied by the existence of a pseudo-deterministic NC search algorithm.

Added section on saving random bits using pseudo-determinism.

We present a pseudo-deterministic $NC$ algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $poly(n)$ processors, $poly(\log n)$ depth, $poly(\log n)$ random bits, and outputs for each bipartite input graph a {\bf unique} perfect matching with high probability. That is, on the same graph it returns the same matching for almost all choices of randomness.

Furthermore, we prove that if $NC = RNC,$ then the bipartite perfect matching search problem is solvable by a deterministic $NC$ search algorithm. This is not implied by previous randomized $RNC$ search algorithms for bipartite perfect matching, but is implied by the existence of a pseudo-deterministic $NC$ search algorithm.

As an immediate consequence we also find a pseudo-deterministic $NC$ algorithm for depth first search (DFS), and prove that if $NC = RNC$ then DFS is in $NC.$

New introduction and section reordering.

In this paper we present a pseudo-deterministic $RNC$ algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses $poly(n)$ processors, $poly({\log n})$ depth, $poly(\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 $RNC$ 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^{poly(\log n)}$ (quasi polynomially many) processors, proving that bipartite matching is in quasi-$NC$. 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 $RNC$ algorithm for depth first search (DFS).