{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:44:25Z","timestamp":1750308265838,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2004,6,13]],"date-time":"2004-06-13T00:00:00Z","timestamp":1087084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2004,6,13]]},"DOI":"10.1145\/1007352.1007425","type":"proceedings-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T15:55:38Z","timestamp":1090338938000},"page":"475-485","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Counting complexity classes for numeric computations II"],"prefix":"10.1145","author":[{"given":"Peter","family":"B\u00fcrgisser","sequence":"first","affiliation":[{"name":"Paderborn University, Paderborn, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Felipe","family":"Cucker","sequence":"additional","affiliation":[{"name":"University of Hong Kong, Kowloon, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2004,6,13]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1006\/jsco.1998.0261"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.5555\/49151"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_3_1","DOI":"10.1007\/PL00009443"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1090\/S0894-0347-99-00311-2"},{"key":"e_1_3_2_1_5_1","series-title":"volume Algorithms and Computation in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05355-3","volume-title":"Algorithms in Real Algebraic Geometry","author":"Basu S.","year":"2003","unstructured":"S. Basu , R. Pollack , and M. -F. Roy . Algorithms in Real Algebraic Geometry , volume 10 of volume Algorithms and Computation in Mathematics . Springer Verlag , 2003 . S. Basu, R. Pollack, and M. -F. Roy. Algorithms in Real Algebraic Geometry, volume 10 of volume Algorithms and Computation in Mathematics. Springer Verlag, 2003."},{"key":"e_1_3_2_1_6_1","volume-title":"Hermann","author":"Benedetti R.","year":"1990","unstructured":"R. Benedetti and J. -J. Risler . Real Algebraic and Semi-Algebraic Sets . Hermann , 1990 . R. Benedetti and J. -J. Risler. Real Algebraic and Semi-Algebraic Sets. Hermann, 1990."},{"key":"e_1_3_2_1_7_1","first-page":"125","volume-title":"The mathematics of numerical analysis, number 32 in Lectures in Applied Mathematics","author":"Blum L.","year":"1996","unstructured":"L. Blum , F. Cucker , M. Shub , and S. Smale . Algebraic Settings for the Problem \"P\u2260 NP? \". In The mathematics of numerical analysis, number 32 in Lectures in Applied Mathematics , pages 125 -- 144 . Amer. Math. Soc ., 1996 . L. Blum, F. Cucker, M. Shub, and S. Smale. Algebraic Settings for the Problem \"P\u2260 NP?\". In The mathematics of numerical analysis, number 32 in Lectures in Applied Mathematics, pages 125--144. Amer. Math. Soc., 1996."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.5555\/265020"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_3_2_1_10_1","series-title":"em Ergebnisse der Mathematik und ihrer Grenzgebiete","volume-title":"G\u00e9ometrie alg\u00e9brique r\u00e9elle","author":"Bochnak J.","year":"1987","unstructured":"J. Bochnak , M. Coste , and M. F. Roy . G\u00e9ometrie alg\u00e9brique r\u00e9elle , volume 12 of em Ergebnisse der Mathematik und ihrer Grenzgebiete , 3. Folge. Springer Verlag , 1987 . J. Bochnak, M. Coste, and M. F. Roy. G\u00e9ometrie alg\u00e9brique r\u00e9elle, volume 12 of em Ergebnisse der Mathematik und ihrer Grenzgebiete, 3. Folge. Springer Verlag, 1987."},{"key":"e_1_3_2_1_11_1","volume-title":"Number 139 in GTM","author":"Bredon G. E.","year":"1993","unstructured":"G. E. Bredon . Topology and Geometry . Number 139 in GTM . Springer Verlag , 1993 . G. E. Bredon. Topology and Geometry. Number 139 in GTM. Springer Verlag, 1993."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1112\/blms\/22.6.547"},{"key":"e_1_3_2_1_13_1","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":"B\u00fcrgisser P.","year":"2000","unstructured":"P. B\u00fcrgisser . Completeness and Reduction in Algebraic Complexity Theory , volume 7 of Algorithms and Computation in Mathematics . Springer Verlag , 2000 . P. B\u00fcrgisser. Completeness and Reduction in Algebraic Complexity Theory, volume 7 of Algorithms and Computation in Mathematics. Springer Verlag, 2000."},{"key":"e_1_3_2_1_14_1","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"B\u00fcrgisser P.","year":"1997","unstructured":"P. B\u00fcrgisser , M. Clausen , and M. A. Shokrollahi . Algebraic Complexity Theory , volume 315 of Grundlehren der mathematischen Wissenschaften . Springer Verlag , 1997 . P. B\u00fcrgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der mathematischen Wissenschaften. Springer Verlag, 1997."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1007\/978-3-540-24587-2_64"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.1137\/S0097539702415950"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1145\/62212.62257"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_18_1","DOI":"10.1137\/S0097539794270340"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1145\/225058.225155"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1006\/jcom.1995.1018"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.2307\/1971156"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_22_1","DOI":"10.1016\/0022-4049(90)90159-F"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1016\/S0747-7171(88)80006-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_24_1","DOI":"10.1016\/S0747-7171(88)80005-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1007\/BF01202001"},{"doi-asserted-by":"crossref","unstructured":"R. Hartshorne. Algebraic Geometry. GTM. Springer Verlag 1977. R. Hartshorne. Algebraic Geometry. GTM. Springer Verlag 1977.","key":"e_1_3_2_1_26_1","DOI":"10.1007\/978-1-4757-3849-0"},{"key":"e_1_3_2_1_27_1","volume-title":"Cambridge University Press","author":"Hatcher A.","year":"2002","unstructured":"A. Hatcher . Algebraic Topology . Cambridge University Press , Cambridge , 2002 . A. Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, 2002."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1016\/0304-3975(83)90002-6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1006\/jcom.1993.1031"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_30_1","DOI":"10.1007\/BF02573999"},{"key":"e_1_3_2_1_31_1","first-page":"237","volume-title":"Logic and Algorithmic: An international Symposium held in honor of Ernst Specker","author":"Heintz J.","year":"1982","unstructured":"J. Heintz and C. P. Schnorr . Testing polynomials which are hard to compute . In Logic and Algorithmic: An international Symposium held in honor of Ernst Specker , pages 237 -- 254 . Monogr. No. 30 de l'Enseign. Math. , 1982 . J. Heintz and C. P. Schnorr. Testing polynomials which are hard to compute. In Logic and Algorithmic: An international Symposium held in honor of Ernst Specker, pages 237--254. Monogr. No. 30 de l'Enseign. Math., 1982."},{"key":"e_1_3_2_1_32_1","volume-title":"New Topological Methods in Algebraic Geometry","author":"Hirzebruch F.","year":"1965","unstructured":"F. Hirzebruch . New Topological Methods in Algebraic Geometry . Springer Verlag , 1965 . F. Hirzebruch. New Topological Methods in Algebraic Geometry. Springer Verlag, 1965."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1016\/0304-3975(93)00063-B"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1006\/jcom.1996.0019"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.5555\/795663.796372"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_36_1","DOI":"10.1006\/jcss.1997.1478"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.1016\/S0304-3975(98)00261-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1006\/jcom.1999.0502"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1017\/CBO9781139171472"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1016\/0001-8708(82)90048-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.1016\/S0304-3975(98)00190-X"},{"key":"e_1_3_2_1_42_1","volume-title":"Number 51 in Annals of Math. Studies","author":"Milnor J.","year":"1963","unstructured":"J. Milnor . Morse theory. Number 51 in Annals of Math. Studies . Princeton University Press , 1963 . J. Milnor. Morse theory. Number 51 in Annals of Math. Studies. Princeton University Press, 1963."},{"key":"e_1_3_2_1_43_1","volume-title":"Number 61 in Annals of Math. Studies","author":"Milnor J.","year":"1968","unstructured":"J. Milnor . Singular points of complex hypersurfaces. Number 61 in Annals of Math. Studies . Princeton University Press , 1968 . J. Milnor. Singular points of complex hypersurfaces. Number 61 in Annals of Math. Studies. Princeton University Press, 1968."},{"key":"e_1_3_2_1_44_1","volume-title":"Algebraic Geometry I: Complex Projective Varieties","author":"Mumford D.","year":"1976","unstructured":"D. Mumford . Algebraic Geometry I: Complex Projective Varieties . Springer Verlag , 1976 . D. Mumford. Algebraic Geometry I: Complex Projective Varieties. Springer Verlag, 1976."},{"key":"e_1_3_2_1_45_1","volume-title":"Elements of algebraic topology","author":"Munkres James R.","year":"1984","unstructured":"James R. Munkres . Elements of algebraic topology . Addison-Wesley Publishing Company , Menlo Park, CA , 1984 . James R. Munkres. Elements of algebraic topology. Addison-Wesley Publishing Company, Menlo Park, CA, 1984."},{"key":"e_1_3_2_1_46_1","volume-title":"Computational Complexity","author":"Papadimitriou C. H.","year":"1994","unstructured":"C. H. Papadimitriou . Computational Complexity . Addison-Wesley , 1994 . C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_47_1","DOI":"10.1109\/SFCS.1979.10"},{"key":"e_1_3_2_1_48_1","first-page":"267","volume-title":"Complexity of the generalized mover's problem","author":"Reif J. H.","year":"1987","unstructured":"J. H. Reif . Complexity of the generalized mover's problem . In J. T. Schwartz, M. Sharir, and J. Hopcroft, editors, Planning, Geometry and Complexity of Robot Motion, pages 267 -- 281 . Ablex Publishing Corporation , 1987 . J. H. Reif. Complexity of the generalized mover's problem. In J. T. Schwartz, M. Sharir, and J. Hopcroft, editors, Planning, Geometry and Complexity of Robot Motion, pages 267--281. Ablex Publishing Corporation, 1987."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_49_1","DOI":"10.1007\/978-3-642-96200-4"},{"key":"e_1_3_2_1_50_1","volume-title":"Princeton University Press","author":"Steenrod N.","year":"1965","unstructured":"N. Steenrod . Topology of Fibre Bundles . Princeton University Press , 1965 . N. Steenrod. Topology of Fibre Bundles. Princeton University Press, 1965."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_51_1","DOI":"10.1007\/BF01436566"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_52_1","DOI":"10.1016\/0040-9383(86)90020-0"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_53_1","DOI":"10.1137\/0220053"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_54_1","DOI":"10.1145\/800135.804419"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_55_1","DOI":"10.1016\/0304-3975(79)90044-6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_56_1","DOI":"10.1137\/0208032"},{"key":"e_1_3_2_1_57_1","first-page":"365","volume-title":"Logic and Algorithmic: an International Symposium held in honor of Ernst Speck-er","author":"Valiant L. G.","unstructured":"L. G. Valiant . Reducibility by algebraic projections. In Logic and Algorithmic: an International Symposium held in honor of Ernst Speck-er , volume 30 , pages 365 -- 380 . Monogr . No. 30 de l'Enseign. Math., 1982. L. G. Valiant. Reducibility by algebraic projections. In Logic and Algorithmic: an International Symposium held in honor of Ernst Speck-er, volume 30, pages 365--380. Monogr. No. 30 de l'Enseign. Math., 1982."},{"key":"e_1_3_2_1_58_1","volume-title":"Proc. 33rd FOCS","author":"Yao A. C.","year":"1992","unstructured":"A. C. Yao . Algebraic decision trees and Euler characteristic . In Proc. 33rd FOCS , 1992 . A. C. Yao. Algebraic decision trees and Euler characteristic. In Proc. 33rd FOCS, 1992."}],"event":{"sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC04","name":"STOC04: Symposium of Theory of Computing 2004","location":"Chicago IL USA"},"container-title":["Proceedings of the thirty-sixth annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1007352.1007425","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1007352.1007425","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:23:56Z","timestamp":1750267436000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1007352.1007425"}},"subtitle":["algebraic and semialgebraic sets"],"short-title":[],"issued":{"date-parts":[[2004,6,13]]},"references-count":58,"alternative-id":["10.1145\/1007352.1007425","10.1145\/1007352"],"URL":"https:\/\/doi.org\/10.1145\/1007352.1007425","relation":{},"subject":[],"published":{"date-parts":[[2004,6,13]]},"assertion":[{"value":"2004-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}