{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T22:30:05Z","timestamp":1780612205499,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649693","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"106-117","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1988-7866","authenticated-orcid":false,"given":"V.","family":"Arvind","sequence":"first","affiliation":[{"name":"Institute of Mathematical Sciences, Chennai, India \/ Chennai Mathematical Institute, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7855-7886","authenticated-orcid":false,"given":"Abhranil","family":"Chatterjee","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-3656-8844","authenticated-orcid":false,"given":"Partha","family":"Mukhopadhyay","sequence":"additional","affiliation":[{"name":"Chennai Mathematical Institute, Chennai, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(66)90004-4"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2023.6"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Vikraman Arvind Abhranil Chatterjee and Partha Mukhopadhyay. 2023. Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time. https:\/\/doi.org\/10.48550\/ARXIV.2309.15647 arXiv:2309.15647. 10.48550\/ARXIV.2309.15647","DOI":"10.48550\/ARXIV.2309.15647"},{"key":"e_1_3_2_1_5_1","volume-title":"Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009","author":"Arvind Vikraman","year":"2009","unstructured":"Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan. 2009. Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15-17, 2009, IIT Kanpur, India. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, IIT Kanpur, India. 25\u201336."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(76)90159-9"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90018-8"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.41"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2005.13"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00055"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-23.2.193"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139087193"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2017.01.018"},{"key":"e_1_3_2_1_17_1","volume-title":"Algorithms for orbit closure separation for invariants and semi-invariants of matrices. Algebra & Number Theory, 14(10)","author":"Derksen Harm","year":"2020","unstructured":"Harm Derksen and Visu Makam. 2020. Algorithms for orbit closure separation for invariants and semi-invariants of matrices. Algebra & Number Theory, 14(10) (2020), 2791\u20132813."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4171\/Automata-1"},{"key":"e_1_3_2_1_19_1","volume-title":"Automata, Languages, and Machines (Vol A)","author":"Eilenberg Samuel","unstructured":"Samuel Eilenberg. 1974. Automata, Languages, and Machines (Vol A). Academic Press."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897564"},{"key":"e_1_3_2_1_21_1","unstructured":"Michael Andrew Forbes. 2014. Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. Ph. D. Dissertation. MIT."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.34"},{"key":"e_1_3_2_1_23_1","volume-title":"S\u00e9minaire Lotharingien de Combinatoire [electronic only], 52","author":"Fortin Marc","year":"2004","unstructured":"Marc Fortin and Christophe Reutenauer. 2004. Commutative\/Noncommutative Rank of Linear Matrices and Subspaces of Matrices of Low Rank. S\u00e9minaire Lotharingien de Combinatoire [electronic only], 52 (2004), 01."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.95"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-019-09417-z"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00037-020-00200-Z"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M138836X"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a014"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.35.9.533"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-018-0165-7"},{"key":"e_1_3_2_1_31_1","unstructured":"Pushkar S. Joglekar. 2023. Personal Communication."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_3_2_1_33_1","volume-title":"A First Course in Noncommutative Rings","author":"Lam T.Y.","unstructured":"T.Y. Lam. 2001. A First Course in Noncommutative Rings (Second Edition)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1515\/crelle-2021-0044","article-title":"Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)","volume":"2021","author":"Makam Visu","year":"2019","unstructured":"Visu Makam and Avi Wigderson. 2019. Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties). Journal f\u00fcr die reine und angewandte Mathematik (Crelles Journal), 2021 (2019), 79 \u2013 131.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik (Crelles Journal)"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Richard S. Pierce. 1982. Associative Algebras. Springer-Verlag.","DOI":"10.1007\/978-1-4757-0163-0"},{"key":"e_1_3_2_1_36_1","volume-title":"Polynomial identities in ring theory","author":"Rowen Louis Halle","unstructured":"Louis Halle Rowen. 1980. Polynomial identities in ring theory. Academic Press."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_3_2_1_38_1","first-page":"184","article-title":"Vermeidung von Divisionen","volume":"264","author":"Strassen Volker","year":"1973","unstructured":"Volker Strassen. 1973. Vermeidung von Divisionen.. Journal f\u00fcr die reine und angewandte Mathematik, 264 (1973), 184\u2013202.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2017.12.009"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-09519-5_73"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649693","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:51Z","timestamp":1750291431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":40,"alternative-id":["10.1145\/3618260.3649693","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649693","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}