{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:41:51Z","timestamp":1781077311488,"version":"3.54.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T00:00:00Z","timestamp":1550707200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2019,2,21]]},"abstract":"<jats:p>A fundamental quest in the theory of computing is to understand the power of randomness. It is not known whether every problem with an efficient randomized algorithm also has one that does not use randomness. One of the extensively studied problems under this theme is that of perfect matching. The perfect matching problem has a randomized parallel (NC) algorithm based on the Isolation Lemma of Mulmuley, Vazirani, and Vazirani. It is a long-standing open question whether this algorithm can be derandomized. In this article, we give an almost complete derandomization of the Isolation Lemma for perfect matchings in bipartite graphs. This gives us a deterministic parallel (quasi-NC) algorithm for the bipartite perfect matching problem.<\/jats:p>\n          <jats:p>Derandomization of the Isolation Lemma means that we deterministically construct a weight assignment so that the minimum weight perfect matching is unique. We present three different ways of doing this construction with a common main idea.<\/jats:p>","DOI":"10.1145\/3306208","type":"journal-article","created":{"date-parts":[[2019,2,22]],"date-time":"2019-02-22T17:01:44Z","timestamp":1550854904000},"page":"109-115","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["A deterministic parallel algorithm for bipartite perfect matching"],"prefix":"10.1145","volume":"62","author":[{"given":"Stephen","family":"Fenner","sequence":"first","affiliation":[{"name":"University of South Carolina, Columbia, SC"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rohit","family":"Gurjar","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[{"name":"Aalen University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,2,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1763424.1763483"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s003730200002"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00006-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9204-8"},{"key":"e_1_2_1_7_1","first-page":"449","article-title":"Can","volume":"17","author":"Edmonds J.","year":"1965","unstructured":"Edmonds , J. Paths , trees, and owers. Can . J. Math. 17 ( 1965 ), 449 -- 467 . Edmonds, J. Paths, trees, and owers. Can. J. Math. 17 (1965), 449--467.","journal-title":"J. Math."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","article-title":"On the maximal number of disjoint circuits of a graph","volume":"9","author":"Erd\u00f6s P.","year":"1962","unstructured":"Erd\u00f6s , P. , P\u00f3sa , L . On the maximal number of disjoint circuits of a graph . Publ. Math. Debrecen 9 ( 1962 ), 3 -- 12 . Erd\u00f6s, P., P\u00f3sa, L. On the maximal number of disjoint circuits of a graph. Publ. Math. Debrecen 9 (1962), 3--12.","journal-title":"Publ. Math. Debrecen"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897564"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3061640.3061655"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_13_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming","author":"Goldwasser S.","year":"2017","unstructured":"Goldwasser , S. , Grossman , O. Bipartite perfect matching in pseudo-deterministic NC. In 44th International Colloquium on Automata, Languages, and Programming ( Warsaw, Poland, July 10--14 , 2017 ), ICALP 2017, 13, 87:1--87. Goldwasser, S., Grossman, O. Bipartite perfect matching in pseudo-deterministic NC. In 44th International Colloquium on Automata, Languages, and Programming (Warsaw, Poland, July 10--14, 2017), ICALP 2017, 13, 87:1--87."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.56"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055440"},{"key":"e_1_2_1_16_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP) (Prague, Czech Republic, July 9--13","author":"Gurjar R.","year":"2018","unstructured":"Gurjar , R. , Thierauf , T. , Vishnoi , N.K. Isolating a vertex via lattices: Polytopes with totally unimodular faces. In 45th International Colloquium on Automata, Languages, and Programming (ICALP) (Prague, Czech Republic, July 9--13 , 2018 ), 74: 1--74:14. Gurjar, R., Thierauf, T., Vishnoi, N.K. Isolating a vertex via lattices: Polytopes with totally unimodular faces. In 45th International Colloquium on Automata, Languages, and Programming (ICALP) (Prague, Czech Republic, July 9--13, 2018), 74:1--74:14."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.31"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"e_1_2_1_19_1","volume-title":"Fundamentals of Computation Theory (Berlin\/Wendisch-Rietz (GDR), September 17--21","author":"Lov\u00e1sz L.","year":"1979","unstructured":"Lov\u00e1sz , L. On determinants, matchings, and random algorithms . In Fundamentals of Computation Theory (Berlin\/Wendisch-Rietz (GDR), September 17--21 , 1979 ), 565--574. Lov\u00e1sz, L. On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory (Berlin\/Wendisch-Rietz (GDR), September 17--21, 1979), 565--574."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1096488"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_22_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming (ICALP) (Prague, Czech Republic, July 9--13","author":"Sankowski P.","year":"2018","unstructured":"Sankowski , P. NC algorithms for weighted planar perfect matching and related problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP) (Prague, Czech Republic, July 9--13 , 2018 ), 97: 1--97:16. Sankowski, P. NC algorithms for weighted planar perfect matching and related problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP) (Prague, Czech Republic, July 9--13, 2018), 97:1--97:16."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00202-A"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.70"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190160103"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.03.002"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306208","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:04:21Z","timestamp":1750273461000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,21]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,2,21]]}},"alternative-id":["10.1145\/3306208"],"URL":"https:\/\/doi.org\/10.1145\/3306208","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,2,21]]},"assertion":[{"value":"2019-02-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}