{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:03Z","timestamp":1725490203551},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_16","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"173-185","source":"Crossref","is-referenced-by-count":2,"title":["The Complexity of Tensor Circuit Evaluation"],"prefix":"10.1007","author":[{"given":"Martin","family":"Beaudry","sequence":"first","affiliation":[]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. Texts in Theoretical Computer Science. Springer Verlag, 1995.","DOI":"10.1007\/978-3-642-79235-9"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. A. M. Barrington","year":"1989","unstructured":"D. A. Mix Barrington. Bounded-width polynomial size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences, 38:150\u2013164, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR3","doi-asserted-by":"crossref","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"D. A. M. Barrington","year":"1988","unstructured":"D. A. Mix Barrington and D. Th\u00e9rien. Finite monoids and the fine structure of NC1. Journal of the Association of Computing Machinery, 35:941\u2013952, 1988.","journal-title":"Journal of the Association of Computing Machinery"},{"key":"16_CR4","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/S0019-9958(82)90439-9","volume":"82","author":"A. Blass","year":"1982","unstructured":"A. Blass and Y. Gurevich. On the unique satisfiability problem. Information and Control, 82:80\u201388, 1982.","journal-title":"Information and Control"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/BF01374526","volume":"25","author":"G. Buntrock","year":"1992","unstructured":"G. Buntrock, C. Damm, U. Hertrampf, and C. Meinel. Structure and importance of logspace MOD-classes. Mathematical Systems Theory, 25:223\u2013237, 1992.","journal-title":"Mathematical Systems Theory"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"S. R. Buss. The Boolean formula value problem is in ALOGTIME. In Proceedings of the 19th Symposium on Theory of Computing, pages 123\u2013131. ACM Press, 1987.","DOI":"10.1145\/28395.28409"},{"issue":"4","key":"16_CR7","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"S. R. Buss","year":"1992","unstructured":"S. R. Buss, S. Cook, A. Gupta, and V. Ramachandran. An optimal parallel algorithm for formula evaluation. SI AM Journal on Computing, 21(4):755\u2013780, 1992.","journal-title":"SI AM Journal on Computing"},{"key":"16_CR8","doi-asserted-by":"crossref","unstructured":"C. Damm, M. Holzer, and P. McKenzie. The complexity of tensor calculus. In Proceedings of the 15th Conference on Computational Complexity, pages 70\u201386. IEEE Computer Society Press, 2000.","DOI":"10.1109\/CCC.2000.856737"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"L. Fortnow. One complexity theorist\u2019s view of quantum computing. In Electronic Notes in Theoretical Computer Science, volume 31. Elsevier, 2000.","DOI":"10.1016\/S1571-0661(05)80330-5"},{"issue":"3","key":"16_CR10","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0022-0000(89)90025-1","volume":"39","author":"L. Hemachandra","year":"1989","unstructured":"L. Hemachandra. The strong exponential hierarchy collapses. Journal of Computer and System Sciences, 39(3):299\u2013322, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR11","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. D. Jones","year":"1976","unstructured":"N. D. Jones and W. T. Laaser. Complete problems for deterministic polynomial time. Theoretical Computer Science, 3:105\u2013117, 1976.","journal-title":"Theoretical Computer Science"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"W. Kuich and A. Salomaa. Semirings, Automata, Languages, volume 5 of EATCS Monographs on Theoretical Computer Science. Springer, 1986.","DOI":"10.1007\/978-3-642-69959-7_2"},{"issue":"2","key":"16_CR13","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C. H. Papadimitriou","year":"1984","unstructured":"C. H. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2):244\u2013259, 1984.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR14","unstructured":"W.-H. Steeb. Kronecker Product of Matrices and Applications. Wissenschaftsverlag, Mannheim, 1991."},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"R. Tolimieri, M. An, and Ch. Lu. Algorithms for Discrete Fourier Transform and Convolution. Springer Verlag, 1997.","DOI":"10.1007\/978-1-4757-2767-8"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"L. G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"key":"16_CR17","doi-asserted-by":"crossref","unstructured":"V. Vinay. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proceedings of the 6th Structure in Complexity Theory, pages 270\u2013284. IEEE Computer Society Press, 1991.","DOI":"10.1109\/SCT.1991.160269"},{"key":"16_CR18","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3:23\u201333, 1977.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:27:41Z","timestamp":1556818061000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}