{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T04:49:25Z","timestamp":1725511765394},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709176"},{"type":"electronic","value":"9783540709183"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70918-3_36","type":"book-chapter","created":{"date-parts":[[2007,5,23]],"date-time":"2007-05-23T23:41:23Z","timestamp":1179963683000},"page":"417-428","source":"Crossref","is-referenced-by-count":3,"title":["VPSPACE and a Transfer Theorem over the Reals"],"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":"36_CR1","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., et al.: Complexity and Real Computation. Springer, Heidelberg (1998)"},{"issue":"1","key":"36_CR2","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":"36_CR3","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":"36_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0168-0072(98)00060-8","volume":"99","author":"O. Chapuis","year":"1999","unstructured":"Chapuis, O., Koiran, P.: Saturation and stability in the theory of computation over the reals. Annals of Pure and Applied Logic\u00a099, 1\u201349 (1999)","journal-title":"Annals of Pure and Applied Logic"},{"key":"36_CR5","unstructured":"Charbit, P., et al.: Finding a vector orthogonal to roughly half a collection of vectors. Accepted for publication in Journal of Complexity (2006), Available from \n                    \n                      http:\/\/perso.ens-lyon.fr\/pascal.koiran\/publications.html"},{"issue":"4","key":"36_CR6","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R. Cole","year":"1988","unstructured":"Cole, R.: Parallel merge sort. SIAM J. Comput.\u00a017(4), 770\u2013785 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"36_CR7","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1137\/S0097539794270340","volume":"26","author":"F. Cucker","year":"1997","unstructured":"Cucker, F., Grigoriev, D.: On the power of real Turing machines over binary inputs. SIAM Journal on Computing\u00a026(1), 243\u2013254 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0747-7171(88)80006-3","volume":"5","author":"D. Grigoriev","year":"1988","unstructured":"Grigoriev, D.: Complexity of deciding Tarski algebra. Journal of Symbolic Computation\u00a05, 65\u2013108 (1988)","journal-title":"Journal of Symbolic Computation"},{"key":"36_CR9","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/jcom.1999.0527","volume":"16","author":"D. Grigoriev","year":"2000","unstructured":"Grigoriev, D.: Topological complexity of the range searching. Journal of Complexity\u00a016, 50\u201353 (2000)","journal-title":"Journal of Complexity"},{"key":"36_CR10","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"},{"key":"36_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1007\/11821069_52","volume-title":"Mathematical Foundations of Computer Science 2006","author":"P. Koiran","year":"2006","unstructured":"Koiran, P., Perifel, S.: Valiant\u2019s model: from exponential sums to exponential products. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 596\u2013607. Springer, Heidelberg (2006)"},{"key":"36_CR12","unstructured":"Koiran, P., Perifel, S.: VPSPACE and a Transfer Theorem over the Reals (2006), Available from \n                    \n                      http:\/\/prunel.ccsd.cnrs.fr\/ensl-00103018"},{"key":"36_CR13","unstructured":"Malod, G.: Polyn\u00f4mes et coefficients. PhD thesis, Universit\u00e9 Claude Bernard Lyon 1 (July 2003)"},{"issue":"2","key":"36_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.2307\/2034050","volume":"15","author":"J. Milnor","year":"1964","unstructured":"Milnor, J.: On Betti numbers of real varieties. Proceedings of the American Mathematical Society\u00a015(2), 275\u2013280 (1964)","journal-title":"Proceedings of the American Mathematical Society"},{"key":"36_CR15","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"36_CR16","volume-title":"Les petits cailloux","author":"B. Poizat","year":"1995","unstructured":"Poizat, B.: Les petits cailloux. Al\u00e9as, Lyon (1995)"},{"key":"36_CR17","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals, part 1. Journal of Symbolic Computation\u00a013, 255\u2013299 (1992)","journal-title":"Journal of Symbolic Computation"},{"key":"36_CR18","first-page":"249","volume-title":"Proc. 11th ACM Symposium on Theory of Computing","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proc. 11th ACM Symposium on Theory of Computing, pp. 249\u2013261. ACM Press, New York (1979)"},{"issue":"4","key":"36_CR19","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"L.G. Valiant","year":"1983","unstructured":"Valiant, L.G., et al.: Fast parallel computation of polynomials using few processors. SIAM Journal on Computing\u00a012(4), 641\u2013644 (1983)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","STACS 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70918-3_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:32:08Z","timestamp":1620016328000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70918-3_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709176","9783540709183"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70918-3_36","relation":{},"subject":[]}}