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. https://resolver.caltech.edu/CaltechAUTHORS:20210930-201800462
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Published Version
See Usage Policy. 414kB |
|
PDF
- Submitted Version
See Usage Policy. 438kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210930-201800462
Abstract
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: |
| |||||||||
| 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. | |||||||||
| Funders: |
| |||||||||
| 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 | |||||||||
| DOI: | 10.1137/16m1097870 | |||||||||
| Record Number: | CaltechAUTHORS:20210930-201800462 | |||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20210930-201800462 | |||||||||
| 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 | |||||||||
| Collection: | CaltechAUTHORS | |||||||||
| Deposited By: | Tony Diaz | |||||||||
| Deposited On: | 04 Oct 2021 20:53 | |||||||||
| Last Modified: | 04 Oct 2021 20:53 |
Repository Staff Only: item control page
