Bipartite Perfect Matching in Pseudo-Deterministic NC
© Shafi Goldwasser and Ofer Grossman;. 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 bipa...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137553 |
| _version_ | 1826197782454599680 |
|---|---|
| author | Goldwasser, Shafi Grossman, Ofer |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Goldwasser, Shafi Grossman, Ofer |
| author_sort | Goldwasser, Shafi |
| collection | MIT |
| description | © Shafi Goldwasser and Ofer Grossman;. 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 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 pseudodeterministic 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 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(log2n) bits whereas the previous best randomized algorithm used O(log7n), 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. |
| first_indexed | 2024-09-23T10:53:04Z |
| format | Article |
| id | mit-1721.1/137553 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:53:04Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1375532022-09-30T23:41:54Z Bipartite Perfect Matching in Pseudo-Deterministic NC Goldwasser, Shafi Grossman, Ofer Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Shafi Goldwasser and Ofer Grossman;. 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 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 pseudodeterministic 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 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(log2n) bits whereas the previous best randomized algorithm used O(log7n), 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. 2021-11-05T17:42:16Z 2021-11-05T17:42:16Z 2017 2019-05-29T16:12:03Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/137553 Goldwasser, Shafi and Grossman, Ofer. 2017. "Bipartite Perfect Matching in Pseudo-Deterministic NC." en 10.4230/LIPIcs.ICALP.2017.87 Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Goldwasser, Shafi Grossman, Ofer Bipartite Perfect Matching in Pseudo-Deterministic NC |
| title | Bipartite Perfect Matching in Pseudo-Deterministic NC |
| title_full | Bipartite Perfect Matching in Pseudo-Deterministic NC |
| title_fullStr | Bipartite Perfect Matching in Pseudo-Deterministic NC |
| title_full_unstemmed | Bipartite Perfect Matching in Pseudo-Deterministic NC |
| title_short | Bipartite Perfect Matching in Pseudo-Deterministic NC |
| title_sort | bipartite perfect matching in pseudo deterministic nc |
| url | https://hdl.handle.net/1721.1/137553 |
| work_keys_str_mv | AT goldwassershafi bipartiteperfectmatchinginpseudodeterministicnc AT grossmanofer bipartiteperfectmatchinginpseudodeterministicnc |