{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:53Z","timestamp":1740109493258,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:00:00Z","timestamp":1605744000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:00:00Z","timestamp":1605744000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00037-020-00200-z","type":"journal-article","created":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T22:22:09Z","timestamp":1605824529000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Linear Matroid Intersection is in Quasi-NC"],"prefix":"10.1007","volume":"29","author":[{"given":"Rohit","family":"Gurjar","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,19]]},"reference":[{"key":"200_CR1","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal (2005). Proving Lower Bounds Via Pseudo-random Generators. In FSTTCS, volume 3821 of Lecture Notes in Computer Science, 92\u2013105.","DOI":"10.1007\/11590156_6"},{"key":"200_CR2","unstructured":"Matthew Anderson, Amir Shpilka & Ben\u00a0Lee Volk (2016). Personal communication."},{"key":"200_CR3","doi-asserted-by":"crossref","unstructured":"David A.\u00a0Mix Barrington (1992). Quasipolynomial Size Circuit Classes. In Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 86\u201393. http:\/\/dx.doi.org\/10.1109\/SCT.1992.215383.","DOI":"10.1109\/SCT.1992.215383"},{"key":"200_CR4","doi-asserted-by":"crossref","unstructured":"Stuart\u00a0J. Berkowitz (1984). On computing the determinant in small parallel time using a small number of processors. Information Processing Letters 18(3), 147\u2013150. ISSN 0020-0190.","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"200_CR5","unstructured":"Allan Borodin, Stephen Cook & Nicholas Pippenger (1984). Parallel Computation for Well-endowed Rings and Space-bounded Probabilistic Machines. Information and Control 58(1-3), 113\u2013136. ISSN 0019-9958."},{"key":"200_CR6","doi-asserted-by":"crossref","unstructured":"Richard\u00a0A. Demillo & Richard\u00a0J. Lipton (1978). A probabilistic remark on algebraic program testing. Information Processing Letters 7(4), 193\u2013195. ISSN 0020-0190.","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"200_CR7","doi-asserted-by":"publisher","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71","author":"Jack Edmonds","year":"1967","unstructured":"Edmonds, Jack: Systems of distinct representatives and linear algebra. Journal of research of the National Bureau of Standards 71, 241\u2013245, 1967","journal-title":"Journal of research of the National Bureau of Standards"},{"key":"200_CR8","first-page":"335","volume":"11","author":"Jack Edmonds","year":"1968","unstructured":"Edmonds, Jack: Matroid partition. Mathematics of the Decision Sciences 11, 335\u2013345, 1968","journal-title":"Mathematics of the Decision Sciences"},{"key":"200_CR9","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"Jack Edmonds","year":"1970","unstructured":"Edmonds, Jack: Submodular Functions, Matroids, and Certain Polyhedra. Combinatorial Structures and Their Applications, pp. 69\u201387. Gordon and Breach, New York 1970"},{"key":"200_CR10","unstructured":"Jack Edmonds (1979). Matroid Intersection. In Discrete Optimization I (Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium), E.L.\u00a0Johnson P.L.\u00a0Hammer & B.H. Korte, editors, volume\u00a04, 39\u201349. Elsevier. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167506008708173."},{"key":"200_CR11","doi-asserted-by":"crossref","unstructured":"Stephen Fenner, Rohit Gurjar & Thomas Thierauf (2019). Bipartite Perfect Matching is in Quasi-NC. SIAM Journal on Computing 0(0), STOC16\u2013218\u2013STOC16\u2013235. https:\/\/doi.org\/10.1137\/16M1097870.","DOI":"10.1137\/16M1097870"},{"key":"200_CR12","unstructured":"Stephen\u00a0A. Fenner, Rohit Gurjar & Thomas Thierauf (2016). Bipartite perfect matching is in quasi-NC. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, 754\u2013763."},{"key":"200_CR13","unstructured":"Michael\u00a0A. Forbes (2014). Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. Ph.D. thesis, MIT."},{"key":"200_CR14","unstructured":"Michael\u00a0L. Fredman, J\u00e1nos Koml\u00f3s & Endre Szemer\u00e9di (1984). Storing a Sparse Table with $$O(1)$$ Worst Case Access Time. J. ACM 31(3), 538\u2013544. ISSN 0004-5411. http:\/\/doi.acm.org\/10.1145\/828.1884."},{"key":"200_CR15","unstructured":"James\u00a0F. Geelen (1999). Maximum rank matrix completion. Linear Algebra and its Applications 288, 211\u2013217. ISSN 0024-3795. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0024379598102100."},{"key":"200_CR16","isbn-type":"print","volume-title":"821\u2013830","author":"Rohit Gurjar & Thomas Thierauf (2017). Linear Matroid Intersection is in quasi-NC. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC","year":"2017","unstructured":"Rohit Gurjar & Thomas Thierauf (2017). Linear Matroid Intersection is in quasi-NC. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC: 821\u2013830. ACM, New York, NY, USA 2017. ISBN 978-1-4503-4528-6","ISBN":"https:\/\/id.crossref.org\/isbn\/9781450345286"},{"key":"200_CR17","unstructured":"Rohit Gurjar, Thomas Thierauf & Nisheeth\u00a0K. Vishnoi (2017). Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. CoRR abs\/1708.02222. http:\/\/arxiv.org\/abs\/1708.02222."},{"key":"200_CR18","doi-asserted-by":"crossref","unstructured":"G\u201abor Ivanyos, Marek Karpinski & Nitin Saxena, , : Deterministic polynomial time algorithms for matrix completion problems. SIAM Journal of computing 39(8), 2010, 2010","DOI":"10.1137\/090781231"},{"key":"200_CR19","unstructured":"Valentine Kabanets & Russell Impagliazzo (2003). Derandomizing polynomial identity tests means proving circuit lower bounds. STOC 355\u2013364."},{"key":"200_CR20","unstructured":"Richard\u00a0M. Karp, Eli Upfal & Avi Wigderson (1988). The complexity of parallel search. Journal of Computer and System Sciences 36(2), 225\u2013253. ISSN 0022-0000. http:\/\/www.sciencedirect.com\/science\/article\/pii\/002200008890027X."},{"key":"200_CR21","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz (1985). Computing ears and branchings in parallel. 26th Annual Symposium on Foundations of Computer Science (SFCS 1985) 464\u2013467.","DOI":"10.1109\/SFCS.1985.16"},{"key":"200_CR22","doi-asserted-by":"crossref","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz (1989). Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matem\u00e1tica - Bulletin\/Brazilian Mathematical Society 20(1), 87\u201399. ISSN 1678-7714. http:\/\/dx.doi.org\/10.1007\/BF02585470.","DOI":"10.1007\/BF02585470"},{"key":"200_CR23","doi-asserted-by":"crossref","unstructured":"Ketan Mulmuley, Umesh\u00a0V. Vazirani & Vijay\u00a0V. Vazirani (1987). Matching is as easy as matrix inversion. Combinatorica 7, 105\u2013113. ISSN 0209-9683. http:\/\/dx.doi.org\/10.1007\/BF02579206.","DOI":"10.1007\/BF02579206"},{"key":"200_CR24","doi-asserted-by":"crossref","unstructured":"Murota, Kazuo: Mixed Matrices: Irreducibility and Decomposition. In: Brualdi, Richard A., Friedland, Shmuel, Klee, Victor (eds.) Combinatorial and Graph-Theoretical Problems in Linear Algebra, pp. 39\u201371. Springer, New York, New York, NY 1993. ISBN 978-1-4613-8354-3. http:\/\/dx.doi.org\/10.1007\/978-1-4613-8354-3_2","DOI":"10.1007\/978-1-4613-8354-3_2"},{"key":"200_CR25","doi-asserted-by":"crossref","unstructured":"H.\u00a0Narayanan, Huzur Saran & Vijay\u00a0V. Vazirani (1994). Randomized Parallel Algorithms for Matroid Union and Intersection, With Applications to Arboresences and Edge-Disjoint Spanning Trees. SIAM J. Comput. 23(2), 387\u2013397. http:\/\/dx.doi.org\/10.1137\/S0097539791195245.","DOI":"10.1137\/S0097539791195245"},{"key":"200_CR26","unstructured":"Oxley, James G.: Matroid Theory (Oxford Graduate Texts in Mathematics). Oxford University Press Inc, New York, NY, USA 2006. ISBN 0199202508"},{"key":"200_CR27","unstructured":"Alexander Schrijver (2003). Combinatorial optimization : polyhedra and efficiency. Vol. B. , Matroids, trees, stable sets. chapters 39-69. Algorithms and combinatorics. Springer-Verlag, Berlin, Heidelberg, New York, N.Y., et al. ISBN 3-540-44389-4. http:\/\/opac.inria.fr\/record=b1124843."},{"issue":"4","key":"200_CR28","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"Jacob T Schwartz","year":"1980","unstructured":"Schwartz, Jacob T.: Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM 27(4), 701\u2013717, 1980","journal-title":"Journal of the ACM"},{"key":"200_CR29","unstructured":"L.\u00a0G. Valiant (1979). Completeness Classes in Algebra. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC '79, 249\u2013261. ACM, New York, NY, USA. http:\/\/doi.acm.org\/10.1145\/800135.804419."},{"key":"200_CR30","doi-asserted-by":"crossref","unstructured":"L.\u00a0G. Valiant, S.\u00a0Skyum, S.\u00a0Berkowitz & C.\u00a0Rackoff (1983). Fast parallel computation of polynomials using few processors. SIAM journal of computing 12(4), 641\u2013644. ISSN 0097-5397 (print), 1095-7111 (electronic).","DOI":"10.1137\/0212043"},{"key":"200_CR31","doi-asserted-by":"crossref","unstructured":"Richard Zippel (1979). Probabilistic Algorithms for Sparse Polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (EUROSAM), 216\u2013226. Springer-Verlag. ISBN 3-540-09519-5.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00200-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-020-00200-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-020-00200-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,4]],"date-time":"2020-12-04T18:06:29Z","timestamp":1607105189000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-020-00200-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,19]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["200"],"URL":"https:\/\/doi.org\/10.1007\/s00037-020-00200-z","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2020,11,19]]},"assertion":[{"value":"14 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}