{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:03Z","timestamp":1750694703286},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2011,3]]},"DOI":"10.1007\/s00037-011-0002-8","type":"journal-article","created":{"date-parts":[[2011,4,18]],"date-time":"2011-04-18T03:08:11Z","timestamp":1303096091000},"page":"1-20","source":"Crossref","is-referenced-by-count":10,"title":["Interpolation in Valiant\u2019s Theory"],"prefix":"10.1007","volume":"20","author":[{"given":"Pascal","family":"Koiran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sylvain","family":"Perifel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,4,19]]},"reference":[{"issue":"5","key":"2_CR1","doi-asserted-by":"crossref","first-page":"1987","DOI":"10.1137\/070697926","volume":"38","author":"Eric Allender","year":"2009","unstructured":"Allender Eric, B\u00fcrgisser Peter, Kjeldgaard-Pedersen Johan, Miltersen Peter Bro (2009) On the Complexity of Numerical Analysis. SIAM J. Comput. 38(5): 1987\u20132006","journal-title":"SIAM J. Comput."},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"Lenore Blum, Felipe Cucker, Mike Shub & Steve Smale (1998). Complexity and Real Computation. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0701-6"},{"issue":"1","key":"2_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"Lenore Blum","year":"1989","unstructured":"Blum Lenore, Shub Mike, Smale Steve (1989) On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society 21(1): 1\u201346","journal-title":"Bulletin of the American Mathematical Society"},{"key":"2_CR4","doi-asserted-by":"crossref","unstructured":"Peter B\u00fcrgisser (2000). Completeness and Reduction in Algebraic Complexity Theory. Number 7 in Algorithms and Computation in Mathematics. Springer.","DOI":"10.1007\/978-3-662-04179-6"},{"issue":"4","key":"2_CR5","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/s10208-002-0059-5","volume":"4","author":"Peter B\u00fcrgisser","year":"2004","unstructured":"B\u00fcrgisser Peter (2004) The Complexity of Factors of Multivariate Polynomials. Foundations of Computational Mathematics 4(4): 369\u2013396","journal-title":"Foundations of Computational Mathematics"},{"issue":"1","key":"2_CR6","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/s00037-009-0260-x","volume":"18","author":"Peter B\u00fcrgisser","year":"2009","unstructured":"B\u00fcrgisser Peter (2009) On Defining Integers And Proving Arithmetic Circuit Lower Bounds. Computational Complexity 18(1): 81\u2013103","journal-title":"Computational Complexity"},{"key":"2_CR7","unstructured":"Peter B\u00fcrgisser, Michael Clausen & Mohammad Amin Shokrollahi (1997). Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer."},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Herv\u00e9 Fournier & Pascal Koiran (1998). Are Lower Bounds Easier over the Reals? In STOC, 507\u2013513.","DOI":"10.1145\/276698.276864"},{"key":"2_CR9","unstructured":"Herv\u00e9 Fournier & Pascal Koiran (2000). Lower Bounds Are Not Easier over the Reals: Inside PH. In ICALP, 832\u2013843."},{"issue":"3\u20134","key":"2_CR10","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00037-004-0185-3","volume":"13","author":"Erich Kaltofen","year":"2005","unstructured":"Kaltofen Erich, Villard Gilles (2005) On the complexity of computing determinants. Computational Complexity 13(3\u20134): 91\u2013130","journal-title":"Computational Complexity"},{"key":"2_CR11","first-page":"191","volume":"28","author":"Richard Karp","year":"1982","unstructured":"Karp Richard, Lipton Richard (1982) Turing machines that take advice. L\u2019Enseignement Math\u00e9matique 28: 191\u2013209","journal-title":"L\u2019Enseignement Math\u00e9matique"},{"issue":"3\u20134","key":"2_CR12","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s00037-004-0186-2","volume":"13","author":"Pascal Koiran","year":"2005","unstructured":"Koiran Pascal (2005) Valiant\u2019s model and the cost of computing integers. Computational Complexity 13(3\u20134): 131\u2013146","journal-title":"Computational Complexity"},{"key":"2_CR13","unstructured":"Pascal Koiran & Sylvain Perifel (2006). Valiant\u2019s Model: From Exponential Sums to Exponential Products. In MFCS, 596\u2013607."},{"issue":"50","key":"2_CR14","doi-asserted-by":"crossref","first-page":"5244","DOI":"10.1016\/j.tcs.2009.08.026","volume":"410","author":"Pascal Koiran","year":"2009","unstructured":"Koiran Pascal, Perifel Sylvain (2009) VPSPACE and a transfer theorem over the complex field. Theor. Comput. Sci. 410(50): 5244\u20135251","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"2_CR15","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/s00037-009-0269-1","volume":"18","author":"Pascal Koiran","year":"2009","unstructured":"Koiran Pascal, Perifel Sylvain (2009) VPSPACE and a Transfer Theorem over the Reals. Computational Complexity 18(4): 551\u2013575","journal-title":"Computational Complexity"},{"key":"2_CR16","unstructured":"Guillaume Malod (2003). Polyn\u00f4mes et coefficients. Ph.D. thesis, Universit\u00e9 Claude Bernard Lyon 1. In French, available from http:\/\/tel.archives-ouvertes.fr\/tel-00087399 ."},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Guillaume Malod (2007). The Complexity of Polynomials and Their Coefficient Functions. In IEEE Conference on Computational Complexity, 193\u2013204.","DOI":"10.1109\/CCC.2007.33"},{"key":"2_CR18","unstructured":"Bruno Poizat (1995). Les petits cailloux. Al\u00e9as."},{"issue":"1","key":"2_CR19","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1215\/S0012-7094-95-08105-8","volume":"81","author":"Shub Mike","year":"1995","unstructured":"Mike Shub, Smale Steve (1995) On the intractability of Hilbert\u2019s Nullstellensatz and an algebraic version of \u201cP=NP\u201d. Duke Mathematical Journal 81(1): 47\u201354","journal-title":"Duke Mathematical Journal"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Leslie G. Valiant (1979). Completeness Classes in Algebra. In STOC, 249\u2013261.","DOI":"10.1145\/800135.804419"},{"issue":"3","key":"2_CR21","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"Klaus W Wagner","year":"1986","unstructured":"Wagner Klaus W (1986) The Complexity of Combinatorial Problems with Succinct Input Representation. Acta Inf. 23(3): 325\u2013356","journal-title":"Acta Inf."}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0002-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-011-0002-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-011-0002-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,9]],"date-time":"2019-06-09T23:37:09Z","timestamp":1560123429000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-011-0002-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["2"],"URL":"https:\/\/doi.org\/10.1007\/s00037-011-0002-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]}}}