{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:57:07Z","timestamp":1725469027812},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540377917"},{"type":"electronic","value":"9783540377931"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11821069_52","type":"book-chapter","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T10:25:12Z","timestamp":1156501512000},"page":"596-607","source":"Crossref","is-referenced-by-count":3,"title":["Valiant\u2019s Model: From Exponential Sums to Exponential Products"],"prefix":"10.1007","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","reference":[{"key":"52_CR1","doi-asserted-by":"crossref","unstructured":"Adleman, L.M.: Two theorems on random polynomial time. In: Proceedings of the 19th IEEE symposium on foundations of computer science, October 1978, pp. 75\u201383 (1978)","DOI":"10.1109\/SFCS.1978.37"},{"key":"52_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, Heidelberg (1998)"},{"issue":"1","key":"52_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"Blum, L., Shub, M., Smale, S.: On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society\u00a021(1), 1\u201346 (1989)","journal-title":"Bulletin of the American Mathematical Society"},{"key":"52_CR4","series-title":"Algorithms and Computation in Mathematics","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. Algorithms and Computation in Mathematics, vol.\u00a07. Springer, Heidelberg (2000)"},{"key":"52_CR5","doi-asserted-by":"crossref","unstructured":"Fournier, H., Koiran, P.: Are lower bounds easier over the reals? In: Proc. 30th ACM Symposium on Theory of Computing, pp. 507\u2013513 (1998)","DOI":"10.1145\/276698.276864"},{"key":"52_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1007\/3-540-45022-X_70","volume-title":"Automata, Languages and Programming","author":"H. Fournier","year":"2000","unstructured":"Fournier, H., Koiran, P.: Lower bounds are not easier over the reals: Inside PH. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 832\u2013843. Springer, Heidelberg (2000)"},{"key":"52_CR7","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1006\/jcom.1993.1031","volume":"9","author":"J. Heintz","year":"1993","unstructured":"Heintz, J., Morgenstern, J.: On the intrinsic complexity of elimination theory. Journal of Complexity\u00a09, 471\u2013498 (1993)","journal-title":"Journal of Complexity"},{"key":"52_CR8","first-page":"191","volume":"28","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M., Lipton, R.J.: Turing machines that take advice. L\u2019enseignement math\u00e9matique\u00a028, 191\u2013209 (1982)","journal-title":"L\u2019enseignement math\u00e9matique"},{"key":"52_CR9","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s00037-004-0186-2","volume":"13","author":"P. Koiran","year":"2004","unstructured":"Koiran, P.: Valiant\u2019s model and the cost of computing integers. Computational Complexity\u00a013, 131\u2013146 (2004)","journal-title":"Computational Complexity"},{"issue":"1","key":"52_CR10","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(93)00063-B","volume":"133","author":"P. Koiran","year":"1994","unstructured":"Koiran, P.: Computing over the reals with addition and order. Theoretical Computer Science\u00a0133(1), 35\u201348 (1994)","journal-title":"Theoretical Computer Science"},{"key":"52_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/3-540-58691-1_45","volume-title":"Algorithmic Number Theory","author":"R.J. Lipton","year":"1994","unstructured":"Lipton, R.J.: Straight-line complexity and integer factorization. In: Huang, M.-D.A., Adleman, L.M. (eds.) ANTS 1994. LNCS, vol.\u00a0877, pp. 71\u201379. Springer, Heidelberg (1994)"},{"key":"52_CR12","unstructured":"Malod, G.: Polynmes et coefficients. PhD thesis, Universit Claude Bernard Lyon (July 1, 2003)"},{"key":"52_CR13","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"52_CR14","unstructured":"Poizat, B.: Les petits cailloux. Al\u00e9as (1995)"},{"issue":"4","key":"52_CR15","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM\u00a027(4), 701\u2013717 (1980)","journal-title":"Journal of the ACM"},{"issue":"1","key":"52_CR16","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1215\/S0012-7094-95-08105-8","volume":"81","author":"M. Shub","year":"1995","unstructured":"Shub, M., Smale, S.: On the intractability of Hilbert\u2019s Nullstellensatz and an algebraic version of \u201cNP \u2260 P?\u201d. Duke Math. Journal\u00a081(1), 47\u201354 (1995)","journal-title":"Duke Math. Journal"},{"key":"52_CR17","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proc. 11th ACM Symposium on Theory of Computing, pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11821069_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:30:44Z","timestamp":1619508644000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11821069_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540377917","9783540377931"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/11821069_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}