{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:51Z","timestamp":1740109491709,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,30]],"date-time":"2016-11-30T00:00:00Z","timestamp":1480464000000},"content-version":"unspecified","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,3]]},"DOI":"10.1007\/s00037-016-0148-5","type":"journal-article","created":{"date-parts":[[2016,11,30]],"date-time":"2016-11-30T04:37:08Z","timestamp":1480480628000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the hardness of the noncommutative determinant"],"prefix":"10.1007","volume":"27","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Srikanth","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,11,30]]},"reference":[{"key":"148_CR1","unstructured":"Vikraman Arvind, Pushkar S. Joglekar & 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, 25\u201336. URL \n                        http:\/\/dx.doi.org\/10.4230\/LIPIcs.FSTTCS.2009.2304\n                        \n                    ."},{"key":"148_CR2","unstructured":"Vikraman Arvind & Srikanth Srinivasan (2010). On the hardness of the noncommutative determinant. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, 677\u2013686. URL \n                        http:\/\/doi.acm.org\/10.1145\/1806689.1806782\n                        \n                    ."},{"key":"148_CR3","doi-asserted-by":"crossref","unstructured":"Helmer Aslaksen (2009). Quaternionic determinants. The Mathematical Intelligencer 18(3), 57\u201365. ISSN 0343-6993. URL \n                        http:\/\/dx.doi.org\/10.1007\/BF03024312\n                        \n                    .","DOI":"10.1007\/BF03024312"},{"key":"148_CR4","doi-asserted-by":"crossref","unstructured":"David A. Mix Barrington (1989). Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1. J. Comput. Syst. Sci. 38(1), 150\u2013164. URL \n                        http:\/\/dx.doi.org\/10.1016\/0022-0000(89)90037-8\n                        \n                    .","DOI":"10.1016\/0022-0000(89)90037-8"},{"key":"148_CR5","unstructured":"Alexander Barvinok (2000). New Permanent Estimators via Non-Commutative Determinants. URL \n                        http:\/\/arxiv.org\/abs\/math\/0007153\n                        \n                    ."},{"key":"148_CR6","doi-asserted-by":"crossref","unstructured":"Richard Beigel & John Gill (1992). Counting Classes: Thresholds, Parity, Mods, and Fewness. Theor. Comput. Sci. 103(1), 3\u201323. URL \n                        http:\/\/dx.doi.org\/10.1016\/0304-3975(92)90084-S\n                        \n                    .","DOI":"10.1016\/0304-3975(92)90084-S"},{"key":"148_CR7","doi-asserted-by":"crossref","unstructured":"Markus Bl\u00e4ser (2015). Noncommutativity makes determinants hard. Inf. Comput. 243, 133\u2013144. URL \n                        http:\/\/dx.doi.org\/10.1016\/j.ic.2014.12.010\n                        \n                    .","DOI":"10.1016\/j.ic.2014.12.010"},{"key":"148_CR8","doi-asserted-by":"crossref","unstructured":"Steve Chien, Prahladh Harsha, Alistair Sinclair & Srikanth Srinivasan (2011). Almost settling the hardness of noncommutative determinant. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, 499\u2013508. URL \n                        http:\/\/doi.acm.org\/10.1145\/1993636.1993703\n                        \n                    .","DOI":"10.1145\/1993636.1993703"},{"key":"148_CR9","doi-asserted-by":"crossref","unstructured":"Steve Chien, Lars Eilstrup Rasmussen & Alistair Sinclair (2003). Clifford algebras and approximating the permanent. J. Comput. Syst. Sci. 67(2), 263\u2013290. URL \n                        http:\/\/dx.doi.org\/10.1016\/S0022-0000(03)00010-2\n                        \n                    .","DOI":"10.1016\/S0022-0000(03)00010-2"},{"key":"148_CR10","doi-asserted-by":"crossref","unstructured":"Steve Chien & Alistair Sinclair (2007). Algebras with Polynomial Identities and Computing the Determinant. SIAM J. Comput. 37(1), 252\u2013266. URL \n                        http:\/\/dx.doi.org\/10.1137\/S0097539705447359\n                        \n                    .","DOI":"10.1137\/S0097539705447359"},{"key":"148_CR11","doi-asserted-by":"crossref","unstructured":"Stephen A. Fenner, Lance Fortnow & Stuart A. Kurtz (1994). Gap-Definable Counting Classes. J. Comput. Syst. Sci. 48(1), 116\u2013148. URL \n                        http:\/\/dx.doi.org\/10.1016\/S0022-0000(05)80024-8\n                        \n                    .","DOI":"10.1016\/S0022-0000(05)80024-8"},{"key":"148_CR12","doi-asserted-by":"crossref","unstructured":"Craig Gentry (2014). Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington\u2019s Theorem. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, 181\u2013187. URL \n                        http:\/\/dx.doi.org\/10.1109\/CCC.2014.26\n                        \n                    .","DOI":"10.1109\/CCC.2014.26"},{"key":"148_CR13","unstructured":"Chris Godsil & Ivan Gutman (1981). On the matching polynomial of a graph. Algebraic Methods in Graph Theory I 241\u2013249."},{"key":"148_CR14","doi-asserted-by":"crossref","unstructured":"Pavel Hrube\u0161, Avi Wigderson & Amir Yehudayoff (2010). Relationless Completeness and Separations. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010, 280\u2013290. URL \n                        http:\/\/doi.ieeecomputersociety.org\/10.1109\/CCC.2010.34\n                        \n                    .","DOI":"10.1109\/CCC.2010.34"},{"key":"148_CR15","doi-asserted-by":"crossref","unstructured":"Narendra Karmarkar, Richard M. Karp, Richard J. Lipton, L\u00e1szl\u00f3 Lov\u00e1sz & Michael Luby (1993). A Monte-Carlo Algorithm for Estimating the Permanent. SIAM J. Comput. 22(2), 284\u2013293. URL \n                        http:\/\/dx.doi.org\/10.1137\/0222021\n                        \n                    .","DOI":"10.1137\/0222021"},{"key":"148_CR16","unstructured":"T.Y. Lam (2005). Introduction to Quadratic Forms over Fields. American Mathematical Soc. ISBN 9780821872413."},{"key":"148_CR17","doi-asserted-by":"crossref","unstructured":"Cristopher Moore & Alexander Russell (2012). Approximating the Permanent via Nonabelian Determinants. SIAM J. Comput. 41(2), 332\u2013355. URL \n                        http:\/\/dx.doi.org\/10.1137\/100806709\n                        \n                    .","DOI":"10.1137\/100806709"},{"key":"148_CR18","unstructured":"Noam Nisan (1991). Lower Bounds for Non-Commutative Computation (Extended Abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, 410\u2013418. URL \n                        http:\/\/doi.acm.org\/10.1145\/103418.103462\n                        \n                    ."},{"key":"148_CR19","doi-asserted-by":"crossref","unstructured":"Ran Raz & Amir Shpilka (2005). Deterministic polynomial identity testing in non-commutative models. Computational Complexity 14(1), 1\u201319. URL \n                        http:\/\/dx.doi.org\/10.1007\/s00037-005-0188-8\n                        \n                    .","DOI":"10.1007\/s00037-005-0188-8"},{"key":"148_CR20","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1979). The Complexity of Computing the Permanent. Theor. Comput. Sci. 8, 189\u2013201. URL \n                        http:\/\/dx.doi.org\/10.1016\/0304-3975(79)90044-6\n                        \n                    .","DOI":"10.1016\/0304-3975(79)90044-6"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0148-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0148-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0148-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,2,26]],"date-time":"2018-02-26T06:27:41Z","timestamp":1519626461000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0148-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,30]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["148"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0148-5","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2016,11,30]]}}}