Perfect Bipartite Matching in Pseudo-Deterministic RNC

by Shafi Goldwasser and Ofer Grossman

Oded's comments

A pseudo-deterministic algorithm for solving a search problem is a randomized algorithm that, with probability at least 2/3, outputs a canonical solution for the given input (or indicates that this input has no solution). The point is that there is a unique solution that is identified as such, as opposed to a general randomized algorithm for a seacrch problem that is only guaranteed to output valid solutions with probability at least 2/3 (but the solutions output on different coin outcomes may be different).

The current work significantly enriches the collection of known a pseudo-deterministic algorithms by presenting an RNC algorithm for finding a perfect matching in bipartite graphs. It builds on techniques presented in the recent (deterministic) quasi-NC algorithm (for the same problem).

In passing, the paper provides a discussion of possible definition of the notion of BPP search problems, but I would suggest a wider range of possibilities and a less categorical tone. The following proposals have some PROs and CONs:

I think it will be interesting the study the relation between these classes, byond the obvious inclusions reflected in the foregoing order.

Add'l Note (Oct'16): The class of search problems having pseudodeterministic PPT algorithms equals the class of search problems that are deterministically (Cook) reducible to the (decision) class BPP. In contrast, each problem in the first foregoing class of ``BPP search problems'' is deterministically (Cook) reducible to the promise class BPP (i.e., the class of promise problems that can be decided by PPT algorithms with two-sided error probability). I find it interesting that the relation between ``search BPP'' and pseudodeterministic PPT is refloected by the relation between the decisional and promise problem versions of BPP.

The original abstract

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(logn) 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

See ECCC TR15-208.

Back to list of Oded's choices.