A Caltech Library Service

Bipartite Perfect Matching is in Quasi-NC

Fenner, Stephen and Gurjar, Rohit and Thierauf, Thomas (2019) Bipartite Perfect Matching is in Quasi-NC. SIAM Journal on Computing, 50 (3). pp. 218-235. ISSN 0097-5397. doi:10.1137/16m1097870.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


We show that the bipartite perfect matching problem is in quasi-NC². That is, it has uniform circuits of quasi-polynomial size n^(O(log n)), and O(log² n) depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2019 Society for Industrial and Applied Mathematics. Received by the editors October 7, 2016; accepted for publication (in revised form) April 12, 2018; published electronically October 24, 2019. A conference version of this paper appeared in the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016) [19]. The second and third authors were supported by DFG grant TH 472/4. We would like to thank Manindra Agrawal and Nitin Saxena for their constant encouragement and very helpful discussions. We thank Arpita Korwar for discussions on some techniques used in section 4, and Jacobo Torán for discussions on the number of shortest cycles. We thank the anonymous reviewers for helpful suggestions.
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)TH 472/4
Subject Keywords:graph matching, parallel complexity, derandomization, quasi-NC, perfect matching, bipartite graphs, parallel algorithms, Isolation Lemma, matching polytope
Issue or Number:3
Classification Code:AMS subject classifications: 68R10, 68W10, 68Q25, 68W20
Record Number:CaltechAUTHORS:20210930-201800462
Persistent URL:
Official Citation:Bipartite Perfect Matching is in Quasi-NC. Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. SIAM Journal on Computing 2021 50:3, STOC16-218-STOC16-235; DOI: 10.1137/16m1097870
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:111130
Deposited By: Tony Diaz
Deposited On:04 Oct 2021 20:53
Last Modified:04 Oct 2021 20:53

Repository Staff Only: item control page