{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T12:21:01Z","timestamp":1648815661262},"reference-count":55,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2003,4,1]],"date-time":"2003-04-01T00:00:00Z","timestamp":1049155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,17]],"date-time":"2013-08-17T00:00:00Z","timestamp":1376697600000},"content-version":"vor","delay-in-days":3791,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Complexity"],"published-print":{"date-parts":[[2003,4]]},"DOI":"10.1016\/s0885-064x(02)00028-6","type":"journal-article","created":{"date-parts":[[2003,3,14]],"date-time":"2003-03-14T20:23:19Z","timestamp":1047673399000},"page":"161-209","source":"Crossref","is-referenced-by-count":4,"title":["Systems of rational polynomial equations have polynomial size approximate zeros on the average"],"prefix":"10.1016","volume":"19","author":[{"given":"D.","family":"Castro","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L.M.","family":"Pardo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"San Mart\u0131\u0301n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0885-064X(02)00028-6_BIB1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1006\/jcom.1997.0432","article-title":"Polar varieties, real equation solving, and data structures","volume":"13","author":"Bank","year":"1997","journal-title":"J. Complexity"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/PL00004896","article-title":"Polar varieties and efficient real elimination","volume":"238","author":"Bank","year":"2001","journal-title":"Math. Z."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB3","doi-asserted-by":"crossref","first-page":"1002","DOI":"10.1145\/235809.235813","article-title":"On the combinatorial and algebraic complexity of quantifier elimination","volume":"43","author":"Basu","year":"1996","journal-title":"J. ACM"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB4","series-title":"Real Algebraic and Semi-algebraic Sets","author":"Benedetti","year":"1990"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB5","series-title":"Complexity and Real Computation","author":"Blum","year":"1998"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB6","unstructured":"J. Bochnak, M. Coste, M.-F. Roy, G\u00e9om\u00e9trie Alg\u00e9brique R\u00e9elle, Ergebnisse der Math., 3. Folge, Band 12, Springer, Berlin, 1987."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB7","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1145\/321662.321664","article-title":"On Euclid's algorithm and the computation of polynomial greatest common divisors","volume":"18","author":"Brown","year":"1971","journal-title":"J. ACM"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB8","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/355791.355795","article-title":"The subresultant PSR algorithm","volume":"4","author":"Brown","year":"1978","journal-title":"ACM Trans. Math. Software"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB9","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/321662.321665","article-title":"On Euclid's algorithm and the theory of subresultants","volume":"18","author":"Brown","year":"1971","journal-title":"J. ACM"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB10","doi-asserted-by":"crossref","unstructured":"D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo, On the hardness of polynomial equation solving, Found. Comput. Math (2003), submitted.","DOI":"10.1007\/s10208-002-0065-7"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB11","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/jcom.2000.0572","article-title":"Kronecker's and Newton's approaches to solving","volume":"17","author":"Castro","year":"2001","journal-title":"J. Complexity"},{"issue":"1","key":"10.1016\/S0885-064X(02)00028-6_BIB12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s002080010017","article-title":"The distribution of condition numbers of rational data of bounded bit length","volume":"1","author":"Castro","year":"2002","journal-title":"Found. Comput. Math."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB13","doi-asserted-by":"crossref","first-page":"1071","DOI":"10.1090\/S0002-9947-99-02275-8","article-title":"On the distribution of points in projective space of bounded height","volume":"352","author":"Choi","year":"2000","journal-title":"Trans. Amer. Math. Soc."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB14","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1145\/321371.321381","article-title":"Subresultants and reduced polynomial remainder sequence","volume":"14","author":"Collins","year":"1967","journal-title":"J. ACM"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB15","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1112\/jlms\/s1-26.3.179","article-title":"On a principle of Lipschitz","volume":"26","author":"Davenport","year":"1951","journal-title":"J. London Math. Soc."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB16","first-page":"370","article-title":"On a problem in the theory of uniform distribution. I","volume":"10","author":"Erd\u00f6s","year":"1948","journal-title":"Indagagtiones. Math."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB17","first-page":"406","article-title":"On a problem in the theory of uniform distribution. II","volume":"10","author":"Erd\u00f6s","year":"1948","journal-title":"Indag. Math."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB18","series-title":"Computational Algebraic Geometry and Commutative Algebra, Proceedings of the Cortona Conference on Computational Algebraic Geometry and Commutative Algebra","first-page":"216","article-title":"La D\u00e9termination des Points Isol\u00e9s et de la Dimension d'une Variet\u00e9 Alg\u00e9brique Peut se Faire en Temps Polynomial","volume":"Vol. XXXIV","author":"Giusti","year":"1993"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB19","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0022-4049(97)00015-7","article-title":"Lower bounds for diophantine approximations","volume":"117 & 118","author":"Giusti","year":"1997","journal-title":"J. Pure Appl. Algebra"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB20","series-title":"Proceedings of the 11th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11","first-page":"205","article-title":"When polynomial equation systems can be \u201cSolved\u201d fast?","volume":"Vol. 948","author":"Giusti","year":"1995"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB21","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1016\/S0764-4442(97)83558-6","article-title":"Le R\u00f4le des Structures de Donn\u00e9es dans les Probl\u00e8mes d\u2019\u00c9limination","volume":"325","author":"Giusti","year":"1997","journal-title":"C. R. Acad. Sci. Paris S\u00e9rie I"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB22","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0022-4049(96)00099-0","article-title":"Straight-line programs in geometric elimination theory","volume":"124","author":"Giusti","year":"1998","journal-title":"J. Pure Appl. Algebra"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB23","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/jcom.2000.0571","article-title":"A Gr\u00f6bner free alternative for polynomial system solving","volume":"17","author":"Giusti","year":"2001","journal-title":"J. Complexity"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB24","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02568028","article-title":"Eine Verallgemeirung des Sturmschen Wurzelz\u00e4hlverfahrens","volume":"21","author":"Habicht","year":"1948","journal-title":"Comment. Math. Helv."},{"issue":"2","key":"10.1016\/S0885-064X(02)00028-6_BIB25","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0022-4049(98)00148-0","article-title":"On the intrinsic complexity of the arithmetic nullstellensatz","volume":"146","author":"H\u00e4gele","year":"2000","journal-title":"J. Pure Appl. Algebra"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB26","series-title":"An Introduction to the Theory of Numbers","author":"Hardy","year":"1938"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB27","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","article-title":"Definability and fast quantifier elimination in algebraically closed fields","volume":"24","author":"Heintz","year":"1983","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10.1016\/S0885-064X(02)00028-6_BIB28","first-page":"37","article-title":"The intrinsic complexity of parametric elimination methods","volume":"1","author":"Heintz","year":"1998","journal-title":"Electron. J. SADIO"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB29","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s002000000046","article-title":"On the time\u2013space complexity of geometric elimination procedures","volume":"11","author":"Heintz","year":"2001","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB30","unstructured":"J. Heintz, C.P. Schnorr, Testing polynomials which are easy to compute, in: Logic and Algorithmic (an International Symposium in Honour of Ernst Specker), Monographie n. 30 de l'Enseignement Math\u00e9matique, 1982, pp. 237\u2013254 (A preliminary version appeared in Proceedings of the 12th Annual ACM Symposium on Computing, 1980, pp. 262\u2013268)."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB31","doi-asserted-by":"crossref","unstructured":"P. Koiran, Approximating the volume of definable sets, in: 36th Annual IEEE Symposium FOCS, 1995, pp. 134\u2013141.","DOI":"10.1109\/SFCS.1995.492470"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB32","doi-asserted-by":"crossref","unstructured":"T. Krick, L.M. Pardo, A computational method for diophantine approximation, in: Algorithms in Algebraic Geometry and Applications, Proceedings MEGA\u201994, Progress in Mathematics, Vol. 143, Birkh\u00e4user, Basel, 1996, pp. 193\u2013254.","DOI":"10.1007\/978-3-0348-9104-2_11"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB33","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1215\/S0012-7094-01-10934-4","article-title":"Sharp estimates for the arithmetic nullstellensatz","volume":"109","author":"Krick","year":"2001","journal-title":"Duke Math. J."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB34","unstructured":"G. Lecerf, Une Alternative aux M\u00e9thodes de R\u00e9\u00e9criture pour la R\u00e9solution des Syst\u00e8mes Alg\u00e9briques, Ph.D. Thesis, \u00c9cole Polytechnique, France, 2001."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB35","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1006\/jsco.2000.0427","article-title":"Sylvester\u2013Habicht sequences and fast cauchy index computation","volume":"31","author":"Lickteig","year":"2001","journal-title":"J. Symb. Comput."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB36","unstructured":"S. Lojasiewicz, Ensembles Semi-Analytiques, Lecture Notes, Institut des Hautes Etudes Scientiques, Presses Universitaires de France, 1966."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB37","series-title":"Computer Algebra, Symbolic and Algebraic Computation","article-title":"Generalised polynomial remainder sequences","author":"Loos","year":"1982"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB38","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1090\/S0002-9939-1964-0161339-9","article-title":"On the Betti numbers of real varieties","volume":"15","author":"Milnor","year":"1964","journal-title":"Proc. Amer. Math. Soc."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01270397","article-title":"Lower bounds for arithmetic networks","volume":"4","author":"Monta\u00f1a","year":"1993","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB40","first-page":"248","article-title":"On some arithmetical results in the geometry of numbers","volume":"1","author":"Mordell","year":"1934","journal-title":"Compositio Math."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB41","first-page":"635","article-title":"Estimates of the Betti numbers of real algebraic hypersurfaces","volume":"70","author":"Oleinik","year":"1951","journal-title":"Mat. Sbornik"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB42","first-page":"399","article-title":"On the topology of real algebraic surfaces","volume":"1","author":"Oleinik","year":"1962","journal-title":"Izv. Akad. Nauk SSSR (in Trans. of the Amer. Math. Soc.)"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB43","series-title":"Proceedings of the 11th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11","first-page":"33","article-title":"How lower and upper complexity bounds meet in elimination theory","volume":"Vol. 948","author":"Pardo","year":"1995"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB44","unstructured":"L.M. Pardo, Universal elimination requires exponential running time (Extended Abstract), in: A. Montes (Ed.), Proceedings EACA\u2019 2000, Barcelona, 2000, pp. 25\u201351."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB45","doi-asserted-by":"crossref","unstructured":"M.F. Roy, Basic algorithms in real algebraic geometry and their complexity: from Sturm's theorem to the existential theory of reals, in: F. Broglia (Ed.), Lecture on Real Algebraic Geometry in Memoriam of Mario Raimondo, de Gruyter Expositions in Mathematics, Vol. 23, Walter de Gruyter and Co. 1996, pp. 1\u201367.","DOI":"10.1515\/9783110811117.1"},{"issue":"2","key":"10.1016\/S0885-064X(02)00028-6_BIB46","doi-asserted-by":"crossref","first-page":"365","DOI":"10.2307\/1969640","article-title":"A new decision method for elementary algebra","volume":"60","author":"Seidenberg","year":"1954","journal-title":"Ann. Math."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB47","series-title":"From Topology to Computation: Proceedings of the Smalefest","first-page":"443","article-title":"Some remark's on B\u00e9zout's theorem and complexity theory","author":"Shub","year":"1993"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB48","doi-asserted-by":"crossref","unstructured":"M. Shub, S. Smale, Complexity of B\u00e9zout's theorem II: volumes and probabilities, in: Proceedings MEGA\u2019 92, Progress in Mathematics, Vol. 109, Birkh\u00e4user, Basel, 1993, pp. 267\u2013285.","DOI":"10.1007\/978-1-4612-2752-6_19"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB49","first-page":"459","article-title":"Complexity of B\u00e9zout's theorem I","volume":"6","author":"Shub","year":"1993","journal-title":"J. Amer. Math. Soc."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB50","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0733008","article-title":"Complexity of Bezout's theorem. IV","volume":"33","author":"Shub","year":"1996","journal-title":"SIAM J. Numer. Anal."},{"key":"10.1016\/S0885-064X(02)00028-6_BIB51","series-title":"A Decision Method for Elementary Algebra and Geometry","author":"Tarski","year":"1948"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB52","doi-asserted-by":"crossref","unstructured":"R. Thom, Sur l'Homologie des Vari\u00e9t\u00e9s Alg\u00e9briques R\u00e9elles, in: Differential and Combinatorial Topology, A Symposium in Honor of Marston Morse, Princeton University Press, Princeton, 1965, pp. 255\u2013265.","DOI":"10.1515\/9781400874842-016"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB53","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1090\/S0273-0979-1985-15349-2","article-title":"Some extremal functions in Fourier analysis","volume":"12","author":"Vaaler","year":"1985","journal-title":"Bull. Amer. Math. Soc. (NS)"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB54","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1090\/S0002-9947-1968-0226281-1","article-title":"Lower bounds for approximation by non linear manifolds","volume":"133","author":"Warren","year":"1968","journal-title":"Trans. AMS"},{"key":"10.1016\/S0885-064X(02)00028-6_BIB55","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/BF01475864","article-title":"\u00dcber die Gleichverteilung von Zahlen Modulo 1","volume":"77","author":"Weyl","year":"1916","journal-title":"Math. Ann."}],"container-title":["Journal of Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0885064X02000286?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0885064X02000286?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,27]],"date-time":"2019-03-27T01:58:17Z","timestamp":1553651897000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0885064X02000286"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,4]]},"references-count":55,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,4]]}},"alternative-id":["S0885064X02000286"],"URL":"https:\/\/doi.org\/10.1016\/s0885-064x(02)00028-6","relation":{},"ISSN":["0885-064X"],"issn-type":[{"value":"0885-064X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,4]]}}}