{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:36:21Z","timestamp":1725561381161},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540206958"},{"type":"electronic","value":"9783540245872"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24587-2_64","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T04:59:19Z","timestamp":1280379559000},"page":"625-634","source":"Crossref","is-referenced-by-count":1,"title":["Counting Complexity Classes over the Reals I: The Additive Case"],"prefix":"10.1007","author":[{"given":"Peter","family":"B\u00fcrgisser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe","family":"Cucker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"64_CR1","series-title":"EATCS Monographs on Theoretical Computer Science, 11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J.L. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J.L., D\u00edaz, J., Gabarr\u00f3, J.: Structural Complexity I. EATCS Monographs on Theoretical Computer Science, 11. Springer, Heidelberg (1988)"},{"key":"64_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Lower bounds for algebraic computation trees. In: Proc. 15th ACM STOC, Boston, pp. 80\u201386 (1983)","DOI":"10.1145\/800061.808735"},{"key":"64_CR3","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)"},{"key":"64_CR4","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. Bull. Amer. Math. Soc.\u00a021, 1\u201346 (1989)","journal-title":"Bull. Amer. Math. Soc."},{"key":"64_CR5","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A.B. Borodin","year":"1977","unstructured":"Borodin, A.B.: On relating time and space to size and depth. SIAM J. Comp.\u00a06, 733\u2013744 (1977)","journal-title":"SIAM J. Comp."},{"key":"64_CR6","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":"64_CR7","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume-title":"Algorithmic and Quantitative Real Algebraic Geometry","author":"P. B\u00fcrgisser","year":"2003","unstructured":"B\u00fcrgisser, P.: Lower bounds and real algebraic geometry. In: Basu, S., Gonzales-Vega, L. (eds.) Algorithmic and Quantitative Real Algebraic Geometry. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a060, AMS, Washington DC (2003)"},{"key":"64_CR8","unstructured":"B\u00fcrgisser, P., Cucker, F.: Counting complexity classes over the reals. II: The unrestricted case (in preparation)"},{"key":"64_CR9","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jcom.1995.1018","volume":"11","author":"F. Cucker","year":"1995","unstructured":"Cucker, F., Koiran, P.: Computing over the reals with addition and order: Higher complexity classes. J. Compl.\u00a011, 358\u2013376 (1995)","journal-title":"J. Compl."},{"key":"64_CR10","doi-asserted-by":"crossref","unstructured":"Fournier, H., Koiran, P.: Are lower bounds easier over the reals? In: Proc. 30th ACM STOC, pp. 507\u2013513 (1998)","DOI":"10.1145\/276698.276864"},{"key":"64_CR11","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":"64_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/BFb0016236","volume-title":"Mathematical Foundations of Computer Science 1986","author":"J. zur Gathen von","year":"1986","unstructured":"von zur Gathen, J.: Parallel arithmetic computations: a survey. In: Wiedermann, J., Gruska, J., Rovan, B. (eds.) MFCS 1986. LNCS, vol.\u00a0233, pp. 93\u2013112. Springer, Heidelberg (1986)"},{"key":"64_CR13","volume-title":"Algebraic topology","author":"A. Hatcher","year":"2002","unstructured":"Hatcher, A.: Algebraic topology. Cambridge University Press, Cambridge (2002)"},{"key":"64_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4684-6802-1","volume-title":"Complexity of Real Functions","author":"K.-I. Ko","year":"1991","unstructured":"Ko, K.-I.: Complexity of Real Functions. Birkh\u00e4user, Basel (1991)"},{"key":"64_CR15","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. Theoret. Comp. Sci.\u00a0133, 35\u201347 (1994)","journal-title":"Theoret. Comp. Sci."},{"key":"64_CR16","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","volume":"19","author":"H.R. Lewis","year":"1982","unstructured":"Lewis, H.R., Papadimitriou, C.H.: Symmetric space-bounded computation. Theoret. Comp. Sci.\u00a019, 161\u2013187 (1982)","journal-title":"Theoret. Comp. Sci."},{"key":"64_CR17","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0304-3975(98)00190-X","volume":"242","author":"K. Meer","year":"2000","unstructured":"Meer, K.: Counting problems over the reals. Theoret. Comp. Sci.\u00a0242, 41\u201358 (2000)","journal-title":"Theoret. Comp. Sci."},{"key":"64_CR18","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, 286\u2013303 (1993)","journal-title":"Information and Computation"},{"key":"64_CR19","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. J. ACM\u00a031, 668\u2013676 (1984)","journal-title":"J. ACM"},{"key":"64_CR20","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. J. ACM\u00a035, 740\u2013747 (1988)","journal-title":"J. ACM"},{"key":"64_CR21","first-page":"435","volume":"309","author":"C. Michaux","year":"1989","unstructured":"Michaux, C.: Une remarque \u00e0 propos des machines sur \u211d introduites par Blum, Shub et Smale. C. R. Acad. Sci. Paris\u00a0309, 435\u2013437 (1989)","journal-title":"C. R. Acad. Sci. Paris"},{"key":"64_CR22","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF02579205","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K.: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica\u00a07, 101\u2013104 (1987)","journal-title":"Combinatorica"},{"key":"64_CR23","volume-title":"Elements of algebraic topology","author":"J.R. Munkres","year":"1984","unstructured":"Munkres, J.R.: Elements of algebraic topology. Addison-Wesley Publishing Company, Menlo Park (1984)"},{"key":"64_CR24","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"64_CR25","doi-asserted-by":"crossref","unstructured":"Reif, J.H.: Complexity of the mover\u2019s problem and generalizations. In: Proc. 20th FOCS, pp. 421\u2013427 (1979)","DOI":"10.1109\/SFCS.1979.10"},{"key":"64_CR26","first-page":"267","volume-title":"Planning, Geometry and Complexity of Robot Motion","author":"J.H. Reif","year":"1987","unstructured":"Reif, J.H.: Complexity of the generalized mover\u2019s problem. In: Schwartz, J.T., Sharir, M., Hopcroft, J. (eds.) Planning, Geometry and Complexity of Robot Motion, pp. 267\u2013281. Ablex Publishing Corporation, New Jersey (1987)"},{"key":"64_CR27","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"E. Tardos","year":"1986","unstructured":"Tardos, E.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res.\u00a034, 250\u2013256 (1986)","journal-title":"Oper. Res."},{"issue":"2","key":"64_CR28","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/0220053","volume":"21","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J. Comp.\u00a021(2), 865\u2013877 (1991)","journal-title":"SIAM J. Comp."},{"key":"64_CR29","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"Toda, S., Watanabe, O.: Polynomial time 1-Turing reductions from #ph to #p. Theoret. Comp. Sci.\u00a0100, 205\u2013221 (1992)","journal-title":"Theoret. Comp. Sci."},{"key":"64_CR30","doi-asserted-by":"crossref","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proc. 11th ACM STOC, pp. 249\u2013261 (1979)","DOI":"10.1145\/800135.804419"},{"key":"64_CR31","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoret. Comp. Sci.\u00a08, 189\u2013201 (1979)","journal-title":"Theoret. Comp. Sci."},{"key":"64_CR32","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comp.\u00a08, 410\u2013421 (1979)","journal-title":"SIAM J. Comp."},{"key":"64_CR33","unstructured":"Valiant, L.G.: Reducibility by algebraic projections. In: Logic and Algorithmic: an International Symposium held in honor of Ernst Specker, vol. 30, pp. 365\u2013380. Monogr. No. 30 de l\u2019Enseign. Math. (1982)"},{"key":"64_CR34","unstructured":"Yao, A.C.: Algebraic decision trees and Euler characteristic. In: Proc. 33rd FOCS (1992)"},{"key":"64_CR35","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Decision tree complexity and Betti numbers. In: Proc. 26th ACM STOC (1994)","DOI":"10.1145\/195058.195414"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24587-2_64","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T19:55:54Z","timestamp":1559332554000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24587-2_64"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206958","9783540245872"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24587-2_64","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}