{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T22:37:50Z","timestamp":1780612670035,"version":"3.54.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T00:00:00Z","timestamp":1521676800000},"content-version":"tdm","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":[[2018,12]]},"DOI":"10.1007\/s00037-018-0165-7","type":"journal-article","created":{"date-parts":[[2018,3,22]],"date-time":"2018-03-22T06:14:37Z","timestamp":1521699277000},"page":"561-593","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":43,"title":["Constructive non-commutative rank computation is in deterministic polynomial time"],"prefix":"10.1007","volume":"27","author":[{"given":"G\u00e1bor","family":"Ivanyos","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Youming","family":"Qiao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"K. V.","family":"Subrahmanyam","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,3,22]]},"reference":[{"key":"165_CR1","unstructured":"B. Adsul, S. Nayak & K. V. Subrahmanyam (2007). A geometric approach to the Kronecker problem II: rectangular shapes, invariants of matrices and the Artin\u2013Procesi theorem. Preprint."},{"issue":"3","key":"165_CR2","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1016\/0021-8693(66)90004-4","volume":"3","author":"S.A Amitsur","year":"1966","unstructured":"S. A. Amitsur (1966). Rational identities and applications to algebra and geometry. Journal of Algebra 3(3), 304\u2013359. ISSN 0021-8693.","journal-title":"Journal of Algebra"},{"issue":"04","key":"165_CR3","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1017\/S144678870001795X","volume":"30","author":"M.D. Atkinson","year":"1981","unstructured":"Atkinson M.D., Lloyd S. (1981) Primitive spaces of matrices of bounded rank. Journal of the Australian Mathematical Society (Series A) 30(04): 473\u2013482","journal-title":"Journal of the Australian Mathematical Society (Series A)"},{"key":"165_CR4","unstructured":"George W. Bergman (1969\u20131970). Skew fields of noncommutative rational functions (preliminary version). S\u00e9minaire Sch\u00fctzenberger 1, 1\u201318."},{"issue":"4","key":"165_CR5","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1007\/s00209-006-0008-0","volume":"254","author":"M. B\u00fcrgin","year":"2006","unstructured":"B\u00fcrgin M., Draisma J. (2006) The Hilbert null cone on tuples of matrices and bilinear forms. Mathematische Zeitschrift 254(4): 785\u2013809","journal-title":"Mathematische Zeitschrift"},{"key":"165_CR6","doi-asserted-by":"crossref","unstructured":"Jonathan F. Buss, Gudmund S. Frandsen & Jeffrey O. Shallit (1999). The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. 58(3): 572\u2013596.","DOI":"10.1006\/jcss.1998.1608"},{"key":"165_CR7","unstructured":"Marco Carmosino, Russell Impagliazzo, Valentine Kabanets & Antonina Kolokolova (2015). Tighter Connections between Derandomization and Circuit Lower Bounds. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2015, August 24\u201326, 2015, Princeton, NJ, USA, 645\u2013658. http:\/\/dx.doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2015.645 ."},{"key":"165_CR8","unstructured":"P. M. Cohn (1985). Free Rings and Their Relations. L.M.S. Monographs. Acad. Press. ISBN 9780121791506. First edition 1971."},{"key":"165_CR9","doi-asserted-by":"crossref","unstructured":"P. M. Cohn (1995). Skew Fields: Theory of General Division Rings. Encyclopedia of Mathematics and its Applications. Cambridge University Press. ISBN 9780521432177.","DOI":"10.1017\/CBO9781139087193"},{"issue":"3\u20134","key":"165_CR10","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1142\/S0218196799000205","volume":"9","author":"P.M. Cohn","year":"1999","unstructured":"Cohn P.M., Reutenauer C. (1999) On the construction of the free field. International Journal of Algebra and Computation 9(3\u20134): 307\u2013323","journal-title":"International Journal of Algebra and Computation"},{"key":"165_CR11","doi-asserted-by":"crossref","unstructured":"H. Derksen & V. Makam (2017a). On non-commutative rank and tensor rank. Linear and Multilinear Algebra 1\u201316. Article in Press.","DOI":"10.1080\/03081087.2017.1337058"},{"key":"165_CR12","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.aim.2017.01.018","volume":"310","author":"Harm Derksen","year":"2017","unstructured":"H. Derksen & V. Makam (2017b). Polynomial degree bounds for matrix semi-invariants.Advances in Mathematics 310, 44\u201363.","journal-title":"Advances in Mathematics"},{"issue":"4","key":"165_CR13","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1090\/S0002-9939-00-05698-7","volume":"129","author":"Harm Derksen","year":"2001","unstructured":"Derksen Harm (2001) Polynomial bounds for rings of invariants. Proceedings of the American Mathematical Society 129(4): 955\u2013964","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"3","key":"165_CR14","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1090\/S0894-0347-00-00331-3","volume":"13","author":"Harm Derksen","year":"2000","unstructured":"Derksen Harm, Weyman Jerzy (2000) Semi-invariants of quivers and saturation for Littlewood\u2013Richardson coefficients. Journal of the American Mathematical Society 13(3): 467\u2013479","journal-title":"Journal of the American Mathematical Society"},{"issue":"1","key":"165_CR15","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/BF01236060","volume":"6","author":"M. Domokos","year":"2001","unstructured":"Domokos M., Zubkov A.N. (2001) Semi-invariants of quivers as determinants. Transformation groups 6(1): 9\u201324","journal-title":"Transformation groups"},{"key":"165_CR16","doi-asserted-by":"publisher","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71","author":"Jack. Edmonds","year":"1967","unstructured":"Edmonds Jack. (1967) Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Standards Sect. B 71: 241\u2013245","journal-title":"J. Res. Nat. Bur. Standards Sect. B"},{"issue":"2","key":"165_CR17","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0001-8708(88)90054-0","volume":"70","author":"David Eisenbud","year":"1988","unstructured":"David Eisenbud & Joe Harris (1988). Vector spaces of matrices of low rank. Advances in Mathematics 70(2), 135\u2013155. ISSN 0001-8708.","journal-title":"Advances in Mathematics"},{"key":"165_CR18","unstructured":"M. Fortin & C. Reutenauer (2004). Commutative\/Non-commutative Rank of Linear Matrices and Subspaces of Matrices of Low Rank. S\u00e9minaire Lotharingien de Combinatoire 52, B52f."},{"key":"165_CR19","doi-asserted-by":"crossref","unstructured":"A. Garg, L. Gurvits, R. Oliveira & A. Wigderson (2016). A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. In Proceedings\u2014Annual IEEE Symposium on Foundations of Computer Science, FOCS, 109\u2013117.","DOI":"10.1109\/FOCS.2016.95"},{"key":"165_CR20","doi-asserted-by":"crossref","unstructured":"Willem A. de Graaf, G\u00e1bor Ivanyos & Lajos R\u00f3nyai (1996). Computing Cartan subalgebras of Lie algebras. Applicable Algebra in Engineering, Communication and Computing 7(5): 339\u2013349","DOI":"10.1007\/BF01293593"},{"issue":"3","key":"165_CR21","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/j.jcss.2004.06.003","volume":"69","author":"Leonid Gurvits","year":"2004","unstructured":"Gurvits Leonid (2004) Classical complexity and quantum entanglement. J. Comput. Syst. Sci. 69(3): 448\u2013484","journal-title":"J. Comput. Syst. Sci."},{"key":"165_CR22","doi-asserted-by":"crossref","unstructured":"Pavel Hrube\u0161 & Avi Wigderson (2015). Non-Commutative Arithmetic Circuits with Division. Theory of Computing 11, 357\u2013393. http:\/\/dx.doi.org\/10.4086\/toc.2015.v011a014 .","DOI":"10.4086\/toc.2015.v011a014"},{"issue":"3","key":"165_CR23","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s00037-016-0143-x","volume":"26","author":"G. Ivanyos","year":"2017","unstructured":"Ivanyos G., Qiao Y., Subrahmanyam K.V. (2017) Non-commutative Edmonds problem and matrix semi-invariants. Computational Complexity 26(3): 717\u2013763","journal-title":"Computational Complexity"},{"key":"165_CR24","doi-asserted-by":"crossref","unstructured":"G\u00e1bor Ivanyos, Marek Karpinski, Youming Qiao & Miklos Santha (2015). Generalized Wong sequences and their applications to Edmonds\u2019 problems. J. Comput. Syst. Sci. 81(7), 1373\u20131386. http:\/\/dx.doi.org\/10.1016\/j.jcss.2015.04.006 .","DOI":"10.1016\/j.jcss.2015.04.006"},{"issue":"1\u20132","key":"165_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"Valentine Kabanets","year":"2004","unstructured":"Kabanets Valentine, Impagliazzo Russell (2004) Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13(1\u20132): 1\u201346","journal-title":"Computational Complexity"},{"issue":"4","key":"165_CR26","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s004930070007","volume":"20","author":"Nathan Linial","year":"2000","unstructured":"Nathan Linial, Alex Samorodnitsky & Avi Wigderson (2000). A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica 20(4), 545\u2013568. http:\/\/dx.doi.org\/10.1007\/s004930070007 .","journal-title":"Combinatorica"},{"issue":"2","key":"165_CR27","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1112\/jlms\/s2-18.2.221","volume":"s2-18","author":"Peter Malcolmson","year":"1978","unstructured":"Malcolmson Peter (1978) A Prime Matrix Ideal Yields a Skew Field. Journal of the London Mathematical Society s2-18(2): 221\u2013233","journal-title":"Journal of the London Mathematical Society"},{"key":"165_CR28","unstructured":"K. G. Ramanathan (1954). Lectures on the Algebraic Theory of Fields. Tata Institute of Fundamental Research, Bombay."},{"issue":"1","key":"165_CR29","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-3577(01)80010-0","volume":"12","author":"Aidan Schofield","year":"2001","unstructured":"Aidan Schofield & Michel Van den Bergh (2001). Semi-invariants of quivers for arbitrary dimension vectors. Indagationes Mathematicae 12(1), 125\u2013138","journal-title":"Indagationes Mathematicae"},{"issue":"2","key":"165_CR30","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0396(74)90014-X","volume":"16","author":"Kai-Tak Wong","year":"1974","unstructured":"Kai-Tak Wong (1974). The eigenvalue problem \u03bb Tx\u00a0+\u00a0Sx. Journal of Differential Equations 16(2), 270\u2013280. ISSN 0022-0396.","journal-title":"Journal of Differential Equations"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-018-0165-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0165-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0165-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,13]],"date-time":"2019-10-13T03:42:52Z","timestamp":1570938172000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-018-0165-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,22]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12]]}},"alternative-id":["165"],"URL":"https:\/\/doi.org\/10.1007\/s00037-018-0165-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,22]]},"assertion":[{"value":"29 November 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2018","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}