{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:43:04Z","timestamp":1725489784817},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540745921"},{"type":"electronic","value":"9783540745938"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74593-8_7","type":"book-chapter","created":{"date-parts":[[2007,8,22]],"date-time":"2007-08-22T07:00:40Z","timestamp":1187766040000},"page":"80-89","source":"Crossref","is-referenced-by-count":0,"title":["Decision Versus Evaluation in Algebraic Complexity"],"prefix":"10.1007","author":[{"given":"Pascal","family":"Koiran","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","unstructured":"Allender, E.: Arithmetic circuits and counting complexity classes. In: Krajicek, J. (ed.) Complexity of Computations and Proofs, Quaderni di Matematica. Seconda Universita di Napoli, vol.\u00a013, pp. 2\u201315 (2004)"},{"key":"7_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":"7_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":"7_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)"},{"issue":"4","key":"7_CR5","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s10208-002-0059-5","volume":"4","author":"P. B\u00fcrgisser","year":"2004","unstructured":"B\u00fcrgisser, P.: The complexity of factors of multivariate polynomials. Foundations of Computational Mathematics\u00a04(4), 369\u2013396 (2004)","journal-title":"Foundations of Computational Mathematics"},{"key":"7_CR6","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":"7_CR7","doi-asserted-by":"crossref","unstructured":"Charbit, P., Jeandel, E., Koiran, P., P\u00e9rifel, S., Thomass\u00e9, S.: Finding a vector orthogonal to roughly half a collection of vectors. Journal of Complexity (to appear, 2007)","DOI":"10.1016\/j.jco.2006.09.005"},{"key":"7_CR8","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1145\/276698.276864","volume-title":"Proc. 30th ACM Symposium on Theory of Computing","author":"H. Fournier","year":"1998","unstructured":"Fournier, H., Koiran, P.: Are lower bounds easier over the reals? In: Proc. 30th ACM Symposium on Theory of Computing, pp. 507\u2013513. ACM Press, New York (1998)"},{"key":"7_CR9","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":"7_CR10","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":"7_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/3-540-46541-3_3","volume-title":"STACS 2000","author":"P. Koiran","year":"2000","unstructured":"Koiran, P.: Circuits versus trees in algebraic complexity. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 35\u201352. Springer, Heidelberg (2000)"},{"key":"7_CR12","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., P\u00e9rifel, 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":"7_CR13","unstructured":"Koiran, P., P\u00e9rifel, S.: VPSACE and a transfer theorem over the complex field (2007), available from http:\/\/perso.ens-lyon.fr\/pascal.koiran"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/978-3-540-70918-3_36","volume-title":"STACS 2007","author":"P. Koiran","year":"2007","unstructured":"Koiran, P., P\u00e9rifel, S.: VPSACE and a transfer theorem over the reals. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol.\u00a04393, pp. 417\u2013428. Springer, Heidelberg (2007), http:\/\/prunel.ccsd.cnrs.fr\/ensl-00103018"},{"key":"7_CR15","unstructured":"Lickteig, T.: Testing polynomials for zero. Internal report, Universit\u00e4t T\u00fcbingen (1988)"},{"key":"7_CR16","unstructured":"Lickteig, T.: On semialgebraic decision complexity. Technical Report TR-90-52, International Computer Science Institute, Berkeley, Habilitationsschrift, Universit\u00e4t T\u00fcbingen (1990)"},{"key":"7_CR17","unstructured":"Malod, G.: Polyn\u00f4mes et coefficients. PhD thesis, Universit\u00e9 Claude Bernard - Lyon\u00a01 (2003)"},{"key":"7_CR18","volume-title":"Proc. 22nd IEEE Conference on Computational Complexity","author":"G. Malod","year":"2007","unstructured":"Malod, G.: The complexity of polynomials and their coefficient functions. In: Proc. 22nd IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos (2007)"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1016\/0885-064X(92)90007-X","volume":"8","author":"K. Meer","year":"1992","unstructured":"Meer, K.: A note on a $P {\\not =} NP$ result for a restricted class of real machines. Journal of Complexity\u00a08, 451\u2013453 (1992)","journal-title":"Journal of Complexity"},{"issue":"2","key":"7_CR20","doi-asserted-by":"publisher","first-page":"286","DOI":"10.1006\/inco.1993.1057","volume":"106","author":"S. Meiser","year":"1993","unstructured":"Meiser, S.: Point location in arrangements of hyperplanes. Information and Computation\u00a0106(2), 286\u2013303 (1993)","journal-title":"Information and Computation"},{"issue":"3","key":"7_CR21","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer auf der Heide","year":"1984","unstructured":"Meyer auf der Heide, F.: A polynomial linear search algorithm for the n-dimensional knapsack problem. Journal of the ACM\u00a031(3), 668\u2013676 (1984)","journal-title":"Journal of the ACM"},{"issue":"3","key":"7_CR22","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1145\/44483.44490","volume":"35","author":"F. Meyer auf der Heide","year":"1988","unstructured":"Meyer auf der Heide, F.: Fast algorithms for n-dimensional restrictions of hard problems. Journal of the ACM\u00a035(3), 740\u2013747 (1988)","journal-title":"Journal of the ACM"},{"key":"7_CR23","unstructured":"Poizat, B.: Les Petits Cailloux. Nur Al-Mantiq Wal-Ma\u2019rifah. vol. 3, Al\u00e9as, Lyon (1995)"},{"key":"7_CR24","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0885-064X(87)90021-5","volume":"3","author":"S. Smale","year":"1987","unstructured":"Smale, S.: On the topology of algorithms. I. Journal of Complexity\u00a03, 81\u201389 (1987)","journal-title":"Journal of Complexity"},{"key":"7_CR25","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)"},{"key":"7_CR26","unstructured":"Valiant, L.G.: Reducibility by algebraic projections. In: Logic and Algorithmic (an International Symposium held in honour of Ernst Specker). Monographie $n^{\\tiny o}$ 30 de L\u2019Enseignement Math\u00e9matique, pp. 365\u2013380 (1982)"},{"issue":"5","key":"7_CR27","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/S0020-0190(97)00073-2","volume":"62","author":"V.A. Vassiliev","year":"1997","unstructured":"Vassiliev, V.A.: On decision trees for orthants. Information Processing Letters\u00a062(5), 265\u2013268 (1997)","journal-title":"Information Processing Letters"},{"key":"7_CR28","first-page":"573","volume-title":"Synthesis of Parallel Algorithms","author":"J. von zur Gathen","year":"1993","unstructured":"von zur Gathen, J.: Parallel linear algebra. In: Reif, J. (ed.) Synthesis of Parallel Algorithms, pp. 573\u2013617. Morgan Kaufmann, San Francisco (1993)"}],"container-title":["Lecture Notes in Computer Science","Machines, Computations, and Universality"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74593-8_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,13]],"date-time":"2023-05-13T17:32:29Z","timestamp":1683999149000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74593-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540745921","9783540745938"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74593-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}