{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T14:01:41Z","timestamp":1725544901810},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424949"},{"type":"electronic","value":"9783540446798"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44679-6_1","type":"book-chapter","created":{"date-parts":[[2010,2,9]],"date-time":"2010-02-09T12:00:37Z","timestamp":1265716837000},"page":"1-10","source":"Crossref","is-referenced-by-count":2,"title":["Complete Problems for Valiant\u2019s Class of qp-Computable Families of Polynomials"],"prefix":"10.1007","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,31]]},"reference":[{"issue":"1","key":"1_CR1","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"M. Ben-Or","year":"1992","unstructured":"Michael Ben-Or and Richard Cleve Computing algebraic formulas using a constant number of registers. SIAM J. Comput., 21(1):54\u201358, 1992.","journal-title":"SIAM J. Comput"},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub, and S. Smale On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the Amer. Math. Soc., 21:1\u201346, 1989.","journal-title":"Bulletin of the Amer. Math. Soc"},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"Peter B\u00fcrgisser. Completeness and Reduction in Algebraic Complexity Theory. Springer, 2000.","DOI":"10.1007\/978-3-662-04179-6"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Peter B\u00fcrgisser, Michael Clausen, and M. Amin Shokrollahi Algebraic Complexity Theory. Springer, 1997.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"1_CR5","first-page":"2","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"Stephen A. Cook A taxonomy of problems with fast parallel algorithms. Information and Computation, 64:2\u201322, 1985.","journal-title":"Information and Computation"},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0747-7171(87)80063-9","volume":"4","author":"J. Gathen von zur","year":"1987","unstructured":"Joachim von zur Gathen Feasible arithmetic computations: Valiant\u2019s hypothesis. J. Symbolic Comput., 4:137\u2013172, 1987.","journal-title":"J. Symbolic Comput"},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1137\/0208010","volume":"8","author":"L. Hyafil","year":"1979","unstructured":"Laurent Hyafil On the parallel evaluation of multivariate polynomials. SIAM J. Comput., 8(2):120\u2013123, 1979.","journal-title":"SIAM J. Comput"},{"issue":"4","key":"1_CR8","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1137\/0217044","volume":"17","author":"G. L. Miller","year":"1988","unstructured":"Gary L. Miller, Vijaya Ramachandran, and Erich Kaltofen Efficient parallel evaluation of straight-line code and arithmetic circuits. SIAM J. Comput., 17(4):686\u2013695, 1988.","journal-title":"SIAM J. Comput"},{"issue":"4","key":"1_CR9","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L.G. Valiant","year":"1983","unstructured":"L.G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff Fast parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641\u2013644, 1983.","journal-title":"SIAM J. Comput"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant Completeness classes in algebra. In Proc. 11th Int. ACM Symp. on Theoryof Computing (STOC), pages 249\u2013261, 1979.","DOI":"10.1145\/800135.804419"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. G. Valiant","year":"1979","unstructured":"Leslie G. Valiant The complexity of computing the permanent. Theoret. Comput. Sci., 8:189\u2013201, 1979.","journal-title":"Theoret. Comput. Sci"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44679-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T17:33:20Z","timestamp":1558805600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44679-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424949","9783540446798"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-44679-6_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}