Published October 24, 2019
| Submitted + Published
Journal Article
Open
Bipartite Perfect Matching is in Quasi-NC
- Creators
- Fenner, Stephen
- Gurjar, Rohit
- Thierauf, Thomas
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.
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.Attached Files
Published - 16m1097870.pdf
Submitted - 1601.06319.pdf
Files
16m1097870.pdf
Files
(853.2 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:aa2ac94028b757452a7844cf0daf22eb
|
414.8 kB | Preview Download |
|
md5:3c1b54883e7cb0049a03f9c749aff76f
|
438.4 kB | Preview Download |
Additional details
- Eprint ID
- 111130
- Resolver ID
- CaltechAUTHORS:20210930-201800462
- TH 472/4
- Deutsche Forschungsgemeinschaft (DFG)
- Created
-
2021-10-04Created from EPrint's datestamp field
- Updated
-
2021-10-04Created from EPrint's last_modified field