Perfect Bipartite Matching in Pseudo-Deterministic RNC

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:

• A class that contains all (polynomially bounded) relations for which solutions can be found and verified in PPT, say with error probability 1/3. This class supports error reduction and equals the deterministic analogue if BPP=P (as calsses of promise problems, see here), but it does not contain the class of all search problems that can be solved in deterministic polynomial time (since the latter class may contain problems for which the validity of solutions cannot be efficiently verified).
• Classes that contains all (polynomially bounded) relations for which solutions can be found in PPT with some specified probability that is bounded away from 1/2. These classes do not seem to support error reduction and it is not clear if they equals the deterministic analogue, even if P=BPP.
• Classes that contains all (polynomially bounded) relations for which solutions can be found in PPT with any desired probability that is given as an auxiliary parameter, where the algorithm's running time may depend on this parameter $p$ (e.g., it may be linearly related to $\log(1-p)^{-1}$). These class have in-built error reduction, and it is not clear if they equals the deterministic analogue, even if P=BPP.

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.