{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:08:19Z","timestamp":1709824099068},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T00:00:00Z","timestamp":1428969600000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00224-015-9630-8","type":"journal-article","created":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T02:09:52Z","timestamp":1428890992000},"page":"506-527","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Arithmetic Complexity of Tensor Contraction"],"prefix":"10.1007","volume":"58","author":[{"given":"Florent","family":"Capelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Durand","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Mengel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,14]]},"reference":[{"issue":"1","key":"9630_CR1","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/s00037-007-0222-0","volume":"16","author":"M Beaudry","year":"2007","unstructured":"Beaudry, M., Holzer, M.: The complexity of tensor circuit evaluation. Comput. Complex. 16(1), 60\u2013111 (2007)","journal-title":"Comput. Complex."},{"key":"9630_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04179-6","volume-title":"Completeness and Reduction in Algebraic Complexity Theory, vol. 7","author":"P B\u00fcrgisser","year":"2000","unstructured":"B\u00fcrgisser, P.: Completeness and Reduction in Algebraic Complexity Theory, vol. 7. Springer, Berlin Heidelberg New York (2000)"},{"issue":"3","key":"9630_CR3","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"SA Cook","year":"1987","unstructured":"Cook, S.A., McKenzie, P.: Problems complete for deterministic logarithmic space. Journal of Algorithms 8(3), 385\u2013394 (1987)","journal-title":"Journal of Algorithms"},{"issue":"1-2","key":"9630_CR4","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1007\/s00037-000-0170-4","volume":"11","author":"C Damm","year":"2002","unstructured":"Damm, C., Holzer, M., McKenzie, P.: The complexity of tensor calculus. Comput. Complex. 11(1-2), 54\u201389 (2002)","journal-title":"Comput. Complex."},{"issue":"1","key":"9630_CR5","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/j.jcss.2013.08.001","volume":"80","author":"A Durand","year":"2014","unstructured":"Durand, A., Mengel, S.: The complexity of weighted counting for acyclic conjunctive queries. J. Comput. Syst. Sci. 80(1), 277\u2013296 (2014)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9630_CR6","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1145\/382780.382783","volume":"48","author":"G Gottlob","year":"2001","unstructured":"Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. J. ACM 48(3), 431\u2013498 (2001)","journal-title":"J. ACM"},{"issue":"0","key":"9630_CR7","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/j.tcs.2012.03.041","volume":"448","author":"P Koiran","year":"2012","unstructured":"Koiran, P.: Arithmetic circuits: the chasm at depth four gets wider. Theor. Comput. Sci. 448(0), 56\u201365 (2012). doi: 10.1016\/j.tcs.2012.03.041","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9630_CR8","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1006\/jcss.2000.1742","volume":"62","author":"C Lautemann","year":"2001","unstructured":"Lautemann, C., McKenzie, P., Schwentick, T., Vollmer, H.: The descriptive complexity approach to logcfl. J. Comput. Syst. Sci. 62(4), 629\u2013652 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"9630_CR9","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1017\/S1474748008000248","volume":"7","author":"G Malod","year":"2005","unstructured":"Malod, G.: Circuits arithm\u00e9tiques et calculs tensoriels. Journal of the Institute of Mathematics of Jussieu 7, 869\u2013893 (2005)","journal-title":"Journal of the Institute of Mathematics of Jussieu"},{"issue":"1","key":"9630_CR10","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1016\/j.jco.2006.09.006","volume":"24","author":"G Malod","year":"2008","unstructured":"Malod, G., Portier, N.: Characterizing Valiant\u2019s algebraic complexity classes. J. Complex. 24(1), 16\u201338 (2008)","journal-title":"J. Complex."},{"key":"9630_CR11","volume-title":"Finite Dimensional Multilinear Algebra, vol. 1","author":"M Marcus","year":"1973","unstructured":"Marcus, M.: Finite Dimensional Multilinear Algebra, vol. 1. M. Dekker, New York (1973)"},{"key":"9630_CR12","doi-asserted-by":"crossref","unstructured":"Mengel, S.: Characterizing arithmetic circuit classes by constraint satisfaction problems - (extended abstract). In: ICALP (1), pp. 700\u2013711 (2011)","DOI":"10.1007\/978-3-642-22006-7_59"},{"key":"9630_CR13","doi-asserted-by":"crossref","unstructured":"Mengel, S.: Arithmetic branching programs with memory. In: Chatterjee, K., Sgall, J. (eds.) Mathematical Foundations of Computer Science 2013. no. 8087 in Lecture Notes in Computer Science, pp. 667\u2013678. Springer, Berlin Heidelberg New York (2013)","DOI":"10.1007\/978-3-642-40313-2_59"},{"key":"9630_CR14","doi-asserted-by":"crossref","unstructured":"Nisan, N.: Lower bounds for non-commutative computation. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 410\u2013418. ACM (1991)","DOI":"10.1145\/103418.103462"},{"key":"9630_CR15","doi-asserted-by":"crossref","unstructured":"Valiant, L.: Completeness classes in algebra. In: Proceedings of the 11th Annual ACM Symposium on Theory of Computing, pp. 249\u2013261. ACM (1979)","DOI":"10.1145\/800135.804419"},{"key":"9630_CR16","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L Valiant","year":"1983","unstructured":"Valiant, L., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12, 641 (1983)","journal-title":"SIAM J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9630-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9630-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9630-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,23]],"date-time":"2019-08-23T06:03:16Z","timestamp":1566540196000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9630-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,14]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["9630"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9630-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,14]]}}}