{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:05:33Z","timestamp":1764781533132,"version":"3.46.0"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T00:00:00Z","timestamp":1755475200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T00:00:00Z","timestamp":1755475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00037-025-00272-9","type":"journal-article","created":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T07:14:34Z","timestamp":1755501274000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Efficient Noncommutative Polynomial Factorization via Higman Linearization"],"prefix":"10.1007","volume":"34","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pushkar S.","family":"Joglekar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,18]]},"reference":[{"key":"272_CR1","doi-asserted-by":"crossref","unstructured":"S.A Amitsur (1966). Rational identities and applications to algebra\nand geometry. Journal of Algebra 3(3), 304\u2013359. ISSN 0021-8693. URL https:\/\/www.sciencedirect.com\/science\/article\/pii\/0021869366900044.","DOI":"10.1016\/0021-8693(66)90004-4"},{"key":"272_CR2","doi-asserted-by":"crossref","unstructured":"S.A. Amitsur & J. Levitzki (1950). Minimal identities for algebras.\nProceedings of the American Mathematical Society 4(2), 449\u2013463.","DOI":"10.1090\/S0002-9939-1950-0036751-9"},{"key":"272_CR3","doi-asserted-by":"crossref","unstructured":"V. Arvind, Pushkar S. Joglekar & Gaurav Rattan (2018). On the complexity of noncommutative polynomial factorization. Inf. Comput.\n262, 22\u201339. URL https:\/\/doi.org\/10.1016\/j.ic.2018.05.009.","DOI":"10.1016\/j.ic.2018.05.009"},{"key":"272_CR4","unstructured":"Vikraman Arvind, Abhranil Chatterjee, Rajit Datta &\nPartha Mukhopadhyay (2020). A Special Case of Rational Identity\nTesting and the Bre\u0161ar-Klep Theorem. In 45th International Symposium\non Mathematical Foundations of Computer Science, MFCS 2020, August\n24-28, 2020, Prague, Czech Republic, Javier Esparza & Daniel Kr\u00e1l\u2019, editors, volume 170 of LIPIcs, 10:1\u201310:14. Schloss Dagstuhl\n- Leibniz-Zentrum f\u00fcr Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2020.10."},{"key":"272_CR5","doi-asserted-by":"crossref","unstructured":"Nicholas R. Baeth & Daniel Smertnig (2015). Factorization theory:\nFrom commutative to noncommutative settings. Journal of Algebra\n441, 475\u2013551.","DOI":"10.1016\/j.jalgebra.2015.06.007"},{"key":"272_CR6","doi-asserted-by":"crossref","unstructured":"Jason Bell, Albert Heinle & Viktor Levandovskyy (2017).\nOn noncommutative finite factorization domains. Transactions of the\nAmerican Mathematical Society 369(4), 2675\u20132695.","DOI":"10.1090\/tran\/6727"},{"key":"272_CR7","doi-asserted-by":"crossref","unstructured":"Elwyn R. Berlekamp (1967). Factoring polynomials over finite fields.\nBell System Technical Journal 46, 1853\u20131859. ISSN 0005\u20138580.","DOI":"10.1002\/j.1538-7305.1967.tb03174.x"},{"key":"272_CR8","doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov & Hoeteck Wee (2005). More on Noncommutative\nPolynomial Identity Testing. In 20th Annual IEEE Conference on\nComputational Complexity (CCC 2005), 11-15 June 2005, San Jose,\nCA, USA, 92\u201399. URL https:\/\/doi.org\/10.1109\/CCC.2005.13.","DOI":"10.1109\/CCC.2005.13"},{"key":"272_CR9","doi-asserted-by":"crossref","unstructured":"W. Burnside (1905). On the condition of reducibility of any group\nof linear substitutions. Proceedings of London Mathematical Society 3,\n430\u2013434.","DOI":"10.1112\/plms\/s2-3.1.430"},{"key":"272_CR10","doi-asserted-by":"crossref","unstructured":"Chi-Ning Chou, Mrinal Kumar & Noam Solomon (2019). Closure\nResults for Polynomial Factorization. Theory Comput. 15, 1\u201334.","DOI":"10.4086\/toc.2019.v015a013"},{"key":"272_CR11","doi-asserted-by":"crossref","unstructured":"P. M. Cohn (2006). Free Ideal Rings and Localization in General Rings.\nNew Mathematical Monographs. Cambridge University Press.","DOI":"10.1017\/CBO9780511542794"},{"key":"272_CR12","unstructured":"P. M. Cohn (2011). Introduction To Ring Theory. Springer. ISBN\n9788184899696."},{"key":"272_CR13","doi-asserted-by":"crossref","unstructured":"Richard A. DeMillo & Richard J. Lipton (1978). A Probabilistic Remark on Algebraic Program Testing. Inf. Process. Lett. 7(4), 193\u2013\n195. URL https:\/\/doi.org\/10.1016\/0020-0190(78)90067-4.","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"272_CR14","doi-asserted-by":"crossref","unstructured":"Harm Derksen & Visu Makam (2017). Polynomial degree bounds\nfor matrix semi-invariants. Advances in Mathematics 310, 44\u201363.\nISSN 0001-8708. URL https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0001870816304042.","DOI":"10.1016\/j.aim.2017.01.018"},{"key":"272_CR15","unstructured":"Michael A. Forbes (2014). Polynomial identity testing of read-once\noblivious algebraic branching programs. Ph.D. thesis, Massachusetts\nInstitute of Technology, Cambridge, MA, USA. URL http:\/\/hdl.handle.net\/1721.1\/89843."},{"key":"272_CR16","doi-asserted-by":"crossref","unstructured":"Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira &\nAvi Wigderson (2020). Operator Scaling: Theory and Applications.\nFound. Comput. Math. 20(2), 223\u2013290. URL https:\/\/doi.org\/10.1007\/s10208-019-09417-z.","DOI":"10.1007\/s10208-019-09417-z"},{"key":"272_CR17","doi-asserted-by":"crossref","unstructured":"Joachim von zur Gathen & J\u00fcrgen Gerhard (2013). Modern\nComputer Algebra (3. ed.). Cambridge University Press. ISBN 978-1-107-03903-2.","DOI":"10.1017\/CBO9781139856065"},{"key":"272_CR18","doi-asserted-by":"crossref","unstructured":"J Helton, Igor Klep & Jurij Vol\u010di\u010d (2020). Factorization of Noncommutative\nPolynomials and Nullstellens\u00e4tze for the Free Algebra. International Mathematics Research Notices 2022(1), 343\u2013372. ISSN\n1073-7928. URL https:\/\/doi.org\/10.1093\/imrn\/rnaa122.","DOI":"10.1093\/imrn\/rnaa122"},{"key":"272_CR19","doi-asserted-by":"crossref","unstructured":"J.W. Helton, Igor Klep & Jurij Vol\u010di\u010d (2018). Geometry of\nfree loci and factorization of noncommutative polynomials. Advances in Mathematics 331, 589\u2013626. ISSN 0001-8708. URL https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0001870818301476.","DOI":"10.1016\/j.aim.2018.04.007"},{"key":"272_CR20","doi-asserted-by":"crossref","unstructured":"Graham Higman (1940). The Units of Group-Rings. Proceedings\nof the London Mathematical Society s2-46(1), 231\u2013248. URL https:\/\/londmathsoc.onlinelibrary.wiley.com\/doi\/abs\/10.1112\/plms\/s2-46.1.231.","DOI":"10.1112\/plms\/s2-46.1.231"},{"key":"272_CR21","doi-asserted-by":"crossref","unstructured":"G\u00e1bor Ivanyos, Youming Qiao & K. V. Subrahmanyam (2017).\nNon-commutative Edmonds\u2019 problem and matrix semi-invariants.\nComput. Complex. 26(3), 717\u2013763. URL https:\/\/doi.org\/10.1007\/s00037-016-0143-x.","DOI":"10.1007\/s00037-016-0143-x"},{"key":"272_CR22","doi-asserted-by":"crossref","unstructured":"G\u00e1bor Ivanyos, Youming Qiao & K. V. Subrahmanyam (2018).\nConstructive non-commutative rank computation is in deterministic\npolynomial time. Comput. Complex. 27(4), 561\u2013593. URL https:\/\/doi.org\/10.1007\/s00037-018-0165-7.","DOI":"10.1007\/s00037-018-0165-7"},{"key":"272_CR23","doi-asserted-by":"crossref","unstructured":"Valentine Kabanets & Russell Impagliazzo (2004). Derandomizing\nPolynomial Identity Tests Means Proving Circuit Lower Bounds.\nComput. Complex. 13(1-2), 1\u201346.","DOI":"10.1007\/s00037-004-0182-6"},{"key":"272_CR24","unstructured":"Erich Kaltofen (1989). Factorization of Polynomials Given by\nStraight-Line Programs. Adv. Comput. Res. 5, 375\u2013412."},{"key":"272_CR25","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen (1992). Polynomial factorization 1987\u20131991. In Proceedings\nof LATIN Conference, Imre Simon, editor, 294\u2013313. Springer\nBerlin Heidelberg. ISBN 978-3-540-47012-0.","DOI":"10.1007\/BFb0023837"},{"key":"272_CR26","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen & Barry M. Trager (1990a). Computing with\nPolynomials Given By Black Boxes for Their Evaluations: Greatest\nCommon Divisors, Factorization, Separation of Numerators and Denominators.\nJ. Symb. Comput. 9(3), 301\u2013320. URL https:\/\/doi.org\/10.1016\/S0747-7171(08)80015-6.","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"272_CR27","doi-asserted-by":"crossref","unstructured":"Erich Kaltofen & Barry M. Trager (1990b). Computing with\nPolynomials Given By Black Boxes for Their Evaluations: Greatest\nCommon Divisors, Factorization, Separation of Numerators and Denominators.\nJ. Symb. Comput. 9(3), 301\u2013320. URL https:\/\/doi.org\/10.1016\/S0747-7171(08)80015-6.","DOI":"10.1016\/S0747-7171(08)80015-6"},{"key":"272_CR28","doi-asserted-by":"crossref","unstructured":"Swastik Kopparty, Shubhangi Saraf & Amir Shpilka (2015a).\nEquivalence of Polynomial Identity Testing and Polynomial Factorization.\nComput. Complex. 24(2), 295\u2013331.","DOI":"10.1007\/s00037-015-0102-y"},{"key":"272_CR29","doi-asserted-by":"crossref","unstructured":"Swastik Kopparty, Shubhangi Saraf & Amir Shpilka (2015b).\nEquivalence of Polynomial Identity Testing and Polynomial Factorization.\nComput. Complex. 24(2), 295\u2013331. URL https:\/\/doi.org\/10.1007\/s00037-015-0102-y.","DOI":"10.1007\/s00037-015-0102-y"},{"key":"272_CR30","doi-asserted-by":"crossref","unstructured":"Arjen K Lenstra, Hendrik W Lenstra & L\u00e1szl\u00f3 Lov\u00e1sz (1982).\nFactoring polynomials with rational coefficients. Mathematische Annalen\n261(4), 515\u2013534. URL https:\/\/doi.org\/10.1007\/BF01457454.","DOI":"10.1007\/BF01457454"},{"key":"272_CR31","doi-asserted-by":"crossref","unstructured":"Noam Nisan (1991). Lower Bounds for Non-Commutative Computation\n(Extended Abstract). In Proceedings of the 23rd Annual\nACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans,\nLouisiana, USA, 410\u2013418. URL http:\/\/doi.acm.org\/10.1145\/103418.103462.","DOI":"10.1145\/103418.103462"},{"key":"272_CR32","doi-asserted-by":"crossref","unstructured":"Ran Raz & Amir Shpilka (2005). Deterministic polynomial identity\ntesting in non-commutative models. Computational Complexity 14(1),\n1\u201319. URL https:\/\/doi.org\/10.1007\/s00037-005-0188-8.","DOI":"10.1007\/s00037-005-0188-8"},{"key":"#cr-split#-272_CR33.1","doi-asserted-by":"crossref","unstructured":"Lajos R\u00f3nyai (1987). Simple Algebras Are Difficult. In Proceedings of","DOI":"10.1145\/28395.28438"},{"key":"#cr-split#-272_CR33.2","unstructured":"the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, Alfred V. Aho, editor, 398-408. ACM."},{"key":"272_CR34","doi-asserted-by":"crossref","unstructured":"Lajos R\u00f3nyai (1990). Computing the Structure of Finite Algebras.\nJ. Symb. Comput. 9(3), 355\u2013373. URL https:\/\/doi.org\/10.1016\/S0747-7171(08)80017-X.","DOI":"10.1016\/S0747-7171(08)80017-X"},{"key":"272_CR35","doi-asserted-by":"crossref","unstructured":"Jacob T. Schwartz (1980). Fast Probabilistic Algorithms for Verification\nof Polynomial Identities. J. ACM 27(4), 701\u2013717. URL https:\/\/doi.org\/10.1145\/322217.322225.","DOI":"10.1145\/322217.322225"},{"key":"272_CR36","doi-asserted-by":"crossref","unstructured":"Richard Zippel (1979). Probabilistic algorithms for sparse polynomials.\nIn Symbolic and Algebraic Computation, EUROSAM \u201979, An International\nSymposiumon Symbolic and Algebraic Computation, Marseille,\nFrance, June 1979, Proceedings, Edward W. Ng, editor, volume 72 of\nLecture Notes in Computer Science, 216\u2013226. Springer. URL https:\/\/doi.org\/10.1007\/3-540-09519-5_73.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00272-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00272-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00272-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:20Z","timestamp":1764781220000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00272-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,18]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["272"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00272-9","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,8,18]]},"assertion":[{"value":"18 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"10"}}