{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:58:01Z","timestamp":1725861481321},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_14","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:50:21Z","timestamp":1468929021000},"page":"171-181","source":"Crossref","is-referenced-by-count":0,"title":["On Hard Instances of Non-Commutative Permanent"],"prefix":"10.1007","author":[{"given":"Christian","family":"Engels","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B. V. Raghavendra","family":"Rao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"14_CR2","unstructured":"Arvind, V., Joglekar, P.S., Srinivasan, S.: Arithmetic circuits and the hadamard product of polynomials. In: FSTTCS, pp. 25\u201336 (2009)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Arvind, V., Srinivasan, S.: On the hardness of the noncommutative determinant. In: STOC, pp. 677\u2013686 (2010)","DOI":"10.1145\/1806689.1806782"},{"issue":"3","key":"14_CR4","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF03024312","volume":"18","author":"H Aslaksen","year":"1996","unstructured":"Aslaksen, H.: Quaternionic determinants. Math. Int. 18(3), 57\u201365 (1996)","journal-title":"Math. Int."},{"issue":"1","key":"14_CR5","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1287\/moor.21.1.65","volume":"21","author":"AI Barvinok","year":"1996","unstructured":"Barvinok, A.I.: Two algorithmic results for the traveling salesman problem. Math. Oper. Res. 21(1), 65\u201384 (1996)","journal-title":"Math. Oper. Res."},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/978-3-642-39206-1_15","volume-title":"Automata, Languages, and Programming","author":"M Bl\u00e4ser","year":"2013","unstructured":"Bl\u00e4ser, M.: Noncommutativity makes determinants hard. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 172\u2013183. Springer, Heidelberg (2013)"},{"key":"14_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04179-6","volume-title":"Completeness and Reduction in Algebraic Complexity Theory","author":"P B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Completeness and Reduction in Algebraic Complexity Theory. Springer, Heidelberg (2000)"},{"issue":"1","key":"14_CR8","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539705447359","volume":"37","author":"S Chien","year":"2007","unstructured":"Chien, S., Sinclair, A.: Algebras with polynomial identities and computing the determinant. SIAM J. Comput. 37(1), 252\u2013266 (2007)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"14_CR9","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/1714450.1714453","volume":"1","author":"S Datta","year":"2010","unstructured":"Datta, S., Kulkarni, R., Limaye, N., Mahajan, M.: Planarity, determinants, permanents, and (unique) matchings. ToCT 1(3), 10 (2010)","journal-title":"ToCT"},{"key":"14_CR10","unstructured":"Engels, C., Raghavendra Rao, B.V.: New Algorithms and Hard Instances for Non-Commutative Computation. ArXiv e-prints, September 2014"},{"key":"14_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1007\/978-3-540-77120-3_13","volume-title":"Algorithms and Computation","author":"U Flarup","year":"2007","unstructured":"Flarup, U., Koiran, P., Lyaudet, L.: On the expressive power of planar perfect matching and permanents of bounded treewidth matrices. In: Tokuyama, T. (ed.) ISAAC 2007. LNCS, vol. 4835, pp. 124\u2013136. Springer, Heidelberg (2007)"},{"issue":"4","key":"14_CR12","first-page":"761","volume":"46","author":"U Flarup","year":"2010","unstructured":"Flarup, U., Lyaudet, L.: On the expressive power of permanents and perfect matchings of matrices of bounded pathwidth\/cliquewidth. ToCS 46(4), 761\u2013791 (2010)","journal-title":"ToCS"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Noncommutative determinant is hard: a simple proof using an extension of barrington\u2019s theorem. In: CCC, pp. 181\u2013187, June 2014","DOI":"10.1109\/CCC.2014.26"},{"key":"14_CR14","unstructured":"Limaye, N., Malod, G., Srinivasan, S.: Lower bounds for non-commutative skew circuits. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 22, p. 22 (2015)"},{"issue":"1","key":"14_CR15","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-011-0024-2","volume":"22","author":"M Mahajan","year":"2013","unstructured":"Mahajan, M., Rao, B.V.R.: Small space analogues of valiant\u2019s classes and the limitations of skew formulas. Comput. Complex. 22(1), 1\u201338 (2013)","journal-title":"Comput. Complex."},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for non-commutative computation (extended abstract). In: STOC, pp. 410\u2013418 (1991)","DOI":"10.1145\/103418.103462"},{"issue":"3\u20134","key":"14_CR17","first-page":"207","volume":"5","author":"A Shpilka","year":"2010","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. FTTS 5(3\u20134), 207\u2013388 (2010)","journal-title":"FTTS"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: STOC 1979, pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"issue":"2","key":"14_CR19","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0747-7171(87)80063-9","volume":"4","author":"J Gathen von zur","year":"1987","unstructured":"von zur Gathen, J.: Feasible arithmetic computations: Valiant\u2019s hypothesis. J. Symb. Comput. 4(2), 137\u2013172 (1987)","journal-title":"J. Symb. Comput."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T07:03:46Z","timestamp":1568185426000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}