{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:33Z","timestamp":1759063533424},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_15","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T13:20:16Z","timestamp":1372771216000},"page":"172-183","source":"Crossref","is-referenced-by-count":4,"title":["Noncommutativity Makes Determinants Hard"],"prefix":"10.1007","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","doi-asserted-by":"crossref","unstructured":"Arvind, V., Srinivasan, S.: On the hardness of the noncommutative determinant. In: Proc. 42nd ACM Symp. on Theory of Comput (STOC), pp. 677\u2013686 (2010)","DOI":"10.1145\/1806689.1806782"},{"issue":"1","key":"15_CR2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/(SICI)1098-2418(1999010)14:1<29::AID-RSA2>3.0.CO;2-X","volume":"14","author":"A. Barvinok","year":"1999","unstructured":"Barvinok, A.: Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor. Random Struct. Algorithms\u00a014(1), 29\u201361 (1999)","journal-title":"Random Struct. Algorithms"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/978-3-540-73420-8_69","volume-title":"Automata, Languages and Programming","author":"M. Bl\u00e4ser","year":"2007","unstructured":"Bl\u00e4ser, M., Dell, H.: Complexity of the cover polynomial. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 801\u2013812. Springer, Heidelberg (2007)"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Chien, S., Harsha, P., Sinclair, A., Srinivasan, S.: Almost settling the hardness of noncommutative determinant. In: Proc. 43rd ACM Symp. on Theory of Comput (STOC), pp. 499\u2013508 (2011)","DOI":"10.1145\/1993636.1993703"},{"issue":"2","key":"15_CR5","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0022-0000(03)00010-2","volume":"67","author":"S. Chien","year":"2003","unstructured":"Chien, S., Sinclair, A.: Algebras with polynomial identities and computing the determinant. J. Comput. Sys. Sci.\u00a067(2), 263\u2013290 (2003)","journal-title":"J. Comput. Sys. Sci."},{"issue":"2","key":"15_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/S0022-0000(03)00010-2","volume":"67","author":"S. Chien","year":"2003","unstructured":"Chien, S., Rasmussen, L., Sinclair, A.: Clifford algebras and approximating the permanent. J. Comput. Sys. Sci.\u00a067(2), 263\u2013290 (2003)","journal-title":"J. Comput. Sys. Sci."},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/978-3-642-14165-2_37","volume-title":"Automata, Languages and Programming","author":"H. Dell","year":"2010","unstructured":"Dell, H., Husfeldt, T., Wahl\u00e9n, M.: Exponential Time Complexity of the Permanent and the Tutte Polynomial. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 426\u2013437. Springer, Heidelberg (2010)"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Drozd, Y.A., Kirichenko, V.V.: Finite dimensional algebras. Springer (1994)","DOI":"10.1007\/978-3-642-76244-4"},{"key":"15_CR9","unstructured":"Godsil, C.D., Gutman, I.: On the matching polynomial of a graph. In: Lov\u00e1sz, L., S\u00f3s, V.T. (eds.) Algebraic Methods in Graph Theory, vol.\u00a01, pp. 241\u2013249. North-Holland (1981)"},{"issue":"4","key":"15_CR10","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1145\/1008731.1008738","volume":"51","author":"M. Jerrum","year":"2004","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM\u00a051(4), 671\u2013697 (2004)","journal-title":"J. ACM"},{"issue":"2","key":"15_CR11","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1137\/0222021","volume":"22","author":"N. Kamarkar","year":"1993","unstructured":"Kamarkar, N., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Luby, M.: A Monte-Carlo algorithm for estimating the permanent. SIAM J. Comput.\u00a022(2), 284\u2013293 (1993)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"15_CR12","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1137\/S0895480198338827","volume":"12","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Vinay, V.: Determinant: Old algorithms and new insights. SIAM J. Discrete Math.\u00a012(4), 474\u2013490 (1999)","journal-title":"SIAM J. Discrete Math."},{"key":"15_CR13","unstructured":"Moore, C., Russell, A.: Approximating the permanent via nonabelian determinants, arXiv:0906.1702 (2009)"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for noncommutative computation. In: Proc. 23rd ACM Symp. on Theory of Comput. (STOC), pp. 410\u2013418 (1991)","DOI":"10.1145\/103418.103462"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comput. Sci.\u00a08, 189\u2013201 (1979)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T05:42:45Z","timestamp":1557898965000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}