{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:12:31Z","timestamp":1784110351784,"version":"3.55.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,9,29]],"date-time":"2018-09-29T00:00:00Z","timestamp":1538179200000},"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":[[2019,9]]},"DOI":"10.1007\/s00037-018-0171-9","type":"journal-article","created":{"date-parts":[[2018,9,29]],"date-time":"2018-09-29T06:06:34Z","timestamp":1538201194000},"page":"471-542","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees"],"prefix":"10.1007","volume":"28","author":[{"given":"Guillaume","family":"Lagarde","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nutan","family":"Limaye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,9,29]]},"reference":[{"issue":"3","key":"171_CR1","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1137\/140975103","volume":"44","author":"Manindra Agrawal","year":"2015","unstructured":"Agrawal, Manindra, Gurjar, Rohit, Korwar, Arpita, Saxena, Nitin: Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM J. Comput. 44(3), 669\u2013697 (2015)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"171_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0304-3975(97)00227-2","volume":"209","author":"Eric Allender","year":"1998","unstructured":"Allender, Eric, Jiao, Jia, Mahajan, Meena, Vinay, V.: Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Theor. Comput. Sci. 209(1\u20132), 47\u201386 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"171_CR3","first-page":"74","volume":"24","author":"Vikraman Arvind","year":"2017","unstructured":"Arvind, Vikraman, Datta, Rajit, Mukhopadhyay, Partha, Raja, S.: Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings. Electronic Colloquium on Computational Complexity (ECCC) 24, 74 (2017)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"171_CR4","first-page":"193","volume":"23","author":"Vikraman Arvind","year":"2016","unstructured":"Arvind, Vikraman, Joglekar, Pushkar S., Mukhopadhyay, Partha, Raja, S.: Identity Testing for +-Regular Noncommutative Arithmetic Circuits. Electronic Colloquium on Computational Complexity (ECCC) 23, 193 (2016a)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"171_CR5","first-page":"25","volume":"2009","author":"Vikraman Arvind","year":"2009","unstructured":"Arvind, Vikraman, Joglekar, Pushkar S., Srinivasan, Srikanth: Arithmetic Circuits and the Hadamard Product of Polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, 25\u201336 (2009)","journal-title":"In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS"},{"key":"171_CR6","first-page":"89","volume":"23","author":"Vikraman Arvind","year":"2016","unstructured":"Arvind, Vikraman, Mukhopadhyay, Partha, Raja, S.: Randomized Polynomial Time Identity Testing for Noncommutative Circuits. Electronic Colloquium on Computational Complexity (ECCC) 23, 89 (2016b)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"4","key":"171_CR7","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00037-010-0299-8","volume":"19","author":"Vikraman Arvind","year":"2010","unstructured":"Arvind, Vikraman, Mukhopadhyay, Partha, Srinivasan, Srikanth: New Results on Noncommutative and Commutative Polynomial Identity Testing. Computational Complexity 19(4), 521\u2013558 (2010)","journal-title":"Computational Complexity"},{"key":"171_CR8","first-page":"28","volume":"21","author":"Vikraman Arvind","year":"2014","unstructured":"Arvind, Vikraman, Raja, S.: The Complexity of Two Register and Skew Arithmetic Computation. Electronic Colloquium on Computational Complexity (ECCC) 21, 28 (2014)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"171_CR9","doi-asserted-by":"crossref","unstructured":"Andrej Bogdanov & Hoeteck Wee (2005). More on Noncommutative Polynomial Identity Testing. In 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 92\u201399","DOI":"10.1109\/CCC.2005.13"},{"issue":"2","key":"171_CR10","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0022-0000(03)00010-2","volume":"67","author":"Steve Chien","year":"2003","unstructured":"Chien, Steve, Rasmussen, Lars Eilstrup, Sinclair, Alistair: Clifford algebras and approximating the permanent. J. Comput. Syst. Sci. 67(2), 263\u2013290 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"171_CR11","unstructured":"Steve Chien & Alistair Sinclair (2004). Algebras with Polynomial Identities and Computing the Determinant. In 45th Symposium on Foundations of Computer Science (FOCS 2004), Proceedings, 352\u2013361"},{"key":"171_CR12","unstructured":"Kenneth Church & Ramesh Patil (1982). Coping with Syntactic Ambiguity or How to Put the Block in the Box on the Table. Comput. Linguist. 8(3-4), 139\u2013149. ISSN 0891-2017"},{"key":"171_CR13","doi-asserted-by":"crossref","unstructured":"Zeev Dvir, Guillaume Malod, Sylvain Perifel & Amir Yehudayoff (2012). Separating multilinear branching programs and formulas. In STOC, Howard\u00a0J. Karloff & Toniann Pitassi, editors, 615\u2013624. ACM. ISBN 978-1-4503-1245-5","DOI":"10.1145\/2213977.2214034"},{"key":"171_CR14","unstructured":"Klim Efremenko, Ankit Garg, Rafael\u00a0Mendes de\u00a0Oliveira & Avi Wigderson (2018). Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, 1:1\u20131:19"},{"key":"171_CR15","first-page":"243","volume":"2013","author":"Michael A Forbes","year":"2013","unstructured":"Forbes, Michael A., Shpilka, Amir: Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. In 54th Annual IEEE Symposium on Foundations of Computer Science. FOCS 2013, 243\u2013252 (2013)","journal-title":"FOCS"},{"issue":"5","key":"171_CR16","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1137\/140990280","volume":"44","author":"Herv\u00e9 Fournier","year":"2015","unstructured":"Fournier, Herv\u00e9, Limaye, Nutan, Malod, Guillaume, Srinivasan, Srikanth: Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication. SIAM J. Comput. 44(5), 1173\u20131201 (2015)","journal-title":"SIAM J. Comput."},{"key":"171_CR17","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2014). Approaching the Chasm at Depth Four. J. ACM 61(6), 33:1\u201333:16","DOI":"10.1145\/2629541"},{"key":"171_CR18","unstructured":"Rohit Gurjar, Arpita Korwar & Nitin Saxena (2016). Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs. In 31st Conference on Computational Complexity, CCC 2016, 29:1\u201329:16"},{"issue":"4","key":"171_CR19","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1007\/s00037-016-0141-z","volume":"26","author":"Rohit Gurjar","year":"2017","unstructured":"Gurjar, Rohit, Korwar, Arpita, Saxena, Nitin, Thierauf, Thomas: Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs. Computational Complexity 26(4), 835\u2013880 (2017)","journal-title":"Computational Complexity"},{"issue":"3","key":"171_CR20","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1090\/S0894-0347-2011-00694-2","volume":"24","author":"Pavel Hrube\u0161","year":"2011","unstructured":"Hrube\u0161, Pavel, Wigderson, Avi, Yehudayoff, Amir: Non-commutative circuits and the sum-of-squares problem. Journal of the American Mathematical Society 24(3), 871\u2013898 (2011)","journal-title":"Journal of the American Mathematical Society"},{"key":"171_CR21","doi-asserted-by":"crossref","unstructured":"Laurent Hyafil (1977). The Power of Commutativity. In FOCS, 171\u2013174","DOI":"10.1109\/SFCS.1977.31"},{"issue":"3","key":"171_CR22","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1145\/322326.322341","volume":"29","author":"Mark Jerrum & Marc Snir","year":"1982","unstructured":"Mark Jerrum & Marc Snir: Some Exact Complexity Results for Straight-Line Computations over Semirings. J. ACM 29(3), 874\u2013897 (1982)","journal-title":"J. ACM"},{"key":"171_CR23","first-page":"61","volume":"2014","author":"Neeraj Kayal","year":"2014","unstructured":"Kayal, Neeraj, Limaye, Nutan, Saha, Chandan, Srinivasan, Srikanth: An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. In 55th IEEE Annual Symposium on Foundations of Computer Science. FOCS 2014, 61\u201370 (2014)","journal-title":"FOCS"},{"key":"171_CR24","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1145\/2591796.2591847","volume":"2014","author":"Neeraj Kayal","year":"2014","unstructured":"Kayal, Neeraj, Saha, Chandan, Saptharishi, Ramprasad: A super-polynomial lower bound for regular arithmetic formulas. In Symposium on Theory of Computing, STOC 2014, 146\u2013153 (2014)","journal-title":"In Symposium on Theory of Computing, STOC"},{"key":"171_CR25","first-page":"364","volume":"2014","author":"Mrinal Kumar & Shubhangi Saraf","year":"2014","unstructured":"Mrinal Kumar & Shubhangi Saraf: On the Power of Homogeneous Depth 4 Arithmetic Circuits. In 55th IEEE Annual Symposium on Foundations of Computer Science. FOCS 2014, 364\u2013373 (2014)","journal-title":"FOCS"},{"key":"171_CR26","unstructured":"Guillaume Lagarde, Nutan Limaye & Srikanth Srinivasan (2017). Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees. In 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, 41:1\u201341:14"},{"key":"171_CR27","first-page":"94","volume":"23","author":"Guillaume Lagarde","year":"2016","unstructured":"Lagarde, Guillaume, Malod, Guillaume, Perifel, Sylvain: Non-commutative computations: lower bounds and polynomial identity testing. Electronic Colloquium on Computational Complexity (ECCC) 23, 94 (2016)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"1","key":"171_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a012","volume":"12","author":"Nutan Limaye","year":"2016","unstructured":"Limaye, Nutan, Malod, Guillaume, Srinivasan, Srikanth: Lower Bounds for Non-Commutative Skew Circuits. Theory of Computing 12(1), 1\u201338 (2016)","journal-title":"Theory of Computing"},{"issue":"1","key":"171_CR29","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.jco.2006.09.006","volume":"24","author":"Guillaume Malod & Natacha Portier","year":"2008","unstructured":"Guillaume Malod & Natacha Portier: Characterizing Valiant's algebraic complexity classes. J. Complexity 24(1), 16\u201338 (2008)","journal-title":"J. Complexity"},{"key":"171_CR30","unstructured":"Noam Nisan (1991). Lower Bounds for Non-Commutative Computation (Extended Abstract). In STOC, 410\u2013418"},{"issue":"3","key":"171_CR31","first-page":"217","volume":"6","author":"Noam Nisan & Avi Wigderson","year":"1997","unstructured":"Noam Nisan & Avi Wigderson: Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity 6(3), 217\u2013234 (1997)","journal-title":"Computational Complexity"},{"key":"171_CR32","doi-asserted-by":"crossref","unstructured":"Ran Raz (2009). Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM 56(2), 8:1\u20138:17","DOI":"10.1145\/1502793.1502797"},{"issue":"1","key":"171_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"Ran Raz & Amir Shpilka","year":"2005","unstructured":"Ran Raz & Amir Shpilka: Deterministic polynomial identity testing in non-commutative models. Computational Complexity 14(1), 1\u201319 (2005)","journal-title":"Computational Complexity"},{"issue":"2","key":"171_CR34","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s00037-009-0270-8","volume":"18","author":"Ran Raz & Amir Yehudayoff","year":"2009","unstructured":"Ran Raz & Amir Yehudayoff: Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity 18(2), 171\u2013207 (2009)","journal-title":"Computational Complexity"},{"key":"171_CR35","first-page":"135","volume":"24","author":"Ramprasad Saptharishi & Anamay Tengse","year":"2017","unstructured":"Ramprasad Saptharishi & Anamay Tengse: Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees. Electronic Colloquium on Computational Complexity (ECCC) 24, 135 (2017)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"171_CR36","first-page":"49","volume":"99","author":"Nitin Saxena","year":"2009","unstructured":"Saxena, Nitin: Progress on Polynomial Identity Testing. Bulletin of the EATCS 99, 49\u201379 (2009)","journal-title":"Bulletin of the EATCS"},{"key":"171_CR37","first-page":"186","volume":"20","author":"Nitin Saxena","year":"2013","unstructured":"Saxena, Nitin: Progress on Polynomial Identity Testing - II. Electronic Colloquium on Computational Complexity (ECCC) 20, 186 (2013)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"issue":"1","key":"171_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/PL00001609","volume":"10","author":"Amir Shpilka & Avi Wigderson","year":"2001","unstructured":"Amir Shpilka & Avi Wigderson: Depth-3 arithmetic circuits over fields of characteristic zero. Computational Complexity 10(1), 1\u201327 (2001)","journal-title":"Computational Complexity"},{"issue":"3\u20134","key":"171_CR39","first-page":"207","volume":"5","author":"Amir Shpilka & Amir Yehudayoff","year":"2010","unstructured":"Amir Shpilka & Amir Yehudayoff: Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5(3\u20134), 207\u2013388 (2010)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"171_CR40","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant, Sven Skyum, S. Berkowitz & Charles Rackoff (1983). Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput. 12(4), 641\u2013644.","DOI":"10.1137\/0212043"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0171-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-018-0171-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-018-0171-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,2]],"date-time":"2022-09-02T23:59:12Z","timestamp":1662163152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-018-0171-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,29]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["171"],"URL":"https:\/\/doi.org\/10.1007\/s00037-018-0171-9","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,29]]},"assertion":[{"value":"6 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2018","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}