ECCC-Report TR15-208https://eccc.weizmann.ac.il/report/2015/208Comments and Revisions published for TR15-208en-usFri, 16 Jun 2017 00:55:04 +0300
Revision 2
| Perfect Bipartite Matching in Pseudo-Deterministic $RNC$ |
Shafi Goldwasser,
Ofer Grossman
https://eccc.weizmann.ac.il/report/2015/208#revision2We 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.Fri, 16 Jun 2017 00:55:04 +0300https://eccc.weizmann.ac.il/report/2015/208#revision2
Revision 1
| Perfect Bipartite Matching in Pseudo-Deterministic $RNC$ |
Shafi Goldwasser,
Ofer Grossman
https://eccc.weizmann.ac.il/report/2015/208#revision1We 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.$Sat, 09 Apr 2016 00:08:38 +0300https://eccc.weizmann.ac.il/report/2015/208#revision1
Paper TR15-208
| Perfect Bipartite Matching in Pseudo-Deterministic $RNC$ |
Shafi Goldwasser,
Ofer Grossman
https://eccc.weizmann.ac.il/report/2015/208In 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).Sat, 26 Dec 2015 01:01:44 +0200https://eccc.weizmann.ac.il/report/2015/208