{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T03:57:35Z","timestamp":1775102255823,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":102,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540601142","type":"print"},{"value":"9783540494409","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60114-7_4","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:43:25Z","timestamp":1330278205000},"page":"33-69","source":"Crossref","is-referenced-by-count":16,"title":["How lower and upper complexity bounds meet in elimination theory"],"prefix":"10.1007","author":[{"given":"Luis M.","family":"Pardo","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"4_CR1","unstructured":"J.L. Balcazar, J.L. D\u00edaz and J. Gabarr\u00f3. \u201cStructural Complexity I\u201d. EATCS Mon. on Theor. Comp. Sci. 11, Springer (1988)."},{"key":"4_CR2","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1982","unstructured":"W. Baur, V. Strassen. \u201cThe complexity of partial derivatives\u201d. Theoret. Comput. Sci. 22 (1982) 317\u2013330.","journal-title":"Theoret. Comput. Sci."},{"key":"4_CR3","unstructured":"D. Bayer. \u201cThe Division Algorithm and the Hilbert Scheme\u201d. Ph. D. Thesis. Harvard University (1982)"},{"key":"4_CR4","unstructured":"D. Bayer, D. Mumford. \u201cWhat can be computed in algebraic geometry?\u201d. In Computational Algebraic Geometry and Commutative Algebra\u201d, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 1\u201349."},{"key":"4_CR5","unstructured":"E. Becker, J.P. Cardinal, M.F. Roy, Z. Szafraniec. \u201cMultivariate Bezoutians, Kronecker symbol and Eisenbud-Levine formula\u201d. To appear in Proc. MEGA'94, Brikha\u00fcsser Progress in Math."},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. \u201cLower Bounds for Algebraic Computation Trees.\u201d In ACM 15 th Symposium on Theory of Computation, (1983) 80\u201386.","DOI":"10.1145\/800061.808735"},{"key":"4_CR7","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(84)90018-8","volume":"18","author":"S.J. Berkowitz","year":"1984","unstructured":"S.J. Berkowitz.\u201cOn computing the determinant in small parallel time using a small number of processors\u201d, Inf. Proc. Letters 18 (1984) 147\u2013150.","journal-title":"Inf. Proc. Letters"},{"key":"4_CR8","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF02398884","volume":"166","author":"C. Berenstein","year":"1991","unstructured":"C. Berenstein and A. Yger. \u201cEffective B\u00e9zout identities in Q[X 1,...,X n]\u201d, Acta Math., 166 (1991) 69\u2013120.","journal-title":"Acta Math."},{"key":"4_CR9","first-page":"363","volume":"24","author":"C. Berenstein","year":"1991","unstructured":"C. Berenstein and A. Yger. \u201cUne Formule de Jacobi et ses cons\u00e9quences\u201d, Ann. Sci. E.N.S., 4 ieme s\u00e9rie, 24 (1991) 363\u2013377.","journal-title":"Ann. Sci. E.N.S., 4ieme s\u00e9rie"},{"issue":"No.2","key":"4_CR10","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1006\/jctb.1993.1020","volume":"57","author":"L. J. Billera","year":"1993","unstructured":"L. J. Billera, I. M. Gel'fand and B. Sturmfels. \u201cDuality and Minors of Secondary Polyhedra.\u201d J. Combinatorial Theory, Vol. 57, No. 2 (1993) 258\u2013268.","journal-title":"J. Combinatorial Theory"},{"issue":"n.1","key":"4_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/S0273-0979-1989-15750-9","volume":"21","author":"L. Blum","year":"1989","unstructured":"L. Blum, M. Shub and S. Smale; \u201cOn a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines\u201d. Bulletin of the Amer. Math. Soc., vol.21, n. 1, (1989) 1\u201346.","journal-title":"Bulletin of the Amer. Math. Soc."},{"key":"4_CR12","first-page":"24","volume-title":"Les Grands Courants de la Pens\u00e9e Math\u00e9matique","author":"E. Borel","year":"1948","unstructured":"E. Borel. \u201cLa d\u00e9finition en math\u00e9matiques\u201d. In Les Grands Courants de la Pens\u00e9e Math\u00e9matique, Cahiers du Sud, Paris, (1948), 24\u201334."},{"key":"4_CR13","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0206054","volume":"6","author":"A. Borodin","year":"1977","unstructured":"A. Borodin. \u201cOn Relating Time and Space to Size and Depth\u201d. SIAM J. on Comp. 6 (1977) 733\u2013744.","journal-title":"SIAM J. on Comp."},{"key":"4_CR14","volume-title":"The Computational Complexity of Algebraic and Numeric Problems","author":"A. Borodin","year":"1972","unstructured":"A. Borodin, J. Munro. \u201cThe Computational Complexity of Algebraic and Numeric Problems\u201d. Elsevier, NY, (1972)."},{"key":"4_CR15","first-page":"845","volume":"312","author":"J.-B. Bost","year":"1991","unstructured":"J.-B. Bost, H. Gillet and C. Soul\u00e9. \u201cUn analogue arithm\u00e9tique du th\u00e9or\u00e8me de B\u00e9zout\u201d, C.R. Acad. Sci. Paris, t. 312, S\u00e9rie I (1991) 845\u2013848.","journal-title":"C.R. Acad. Sci. Paris"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"J.-B. Bost, H. Gillet and C. Soul\u00e9. \u201cHeights of projective varieties and positive Green forms\u201d, Manuscrit I.H.E.S. (1993).","DOI":"10.2307\/2152736"},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"577","DOI":"10.2307\/1971361","volume":"126","author":"D. W. Brownawell","year":"1987","unstructured":"D. W. Brownawell. \u201cBounds for the degree in the Nullstellensatz\u201d, Annals of Math. 126 (1987) 577\u2013591.","journal-title":"Annals of Math."},{"key":"4_CR18","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1090\/S0894-0347-1988-0928261-3","volume":"1","author":"D.W. Brownawell","year":"1988","unstructured":"D.W. Brownawell. \u201cLocal Diophantine Nullstellen inequalities\u201d, J. Amer. Math. Soc. 1 (1988) 311\u2013322.","journal-title":"J. Amer. Math. Soc."},{"key":"4_CR19","first-page":"374","volume-title":"Multidimensional System Theory","author":"B. Buchberger","year":"1985","unstructured":"B. Buchberger. \u201cGr\u00f6bner bases: An algorithmic method in polynomial ideal theory\u201d. In Multidimensional System Theory (N.K. Bose, ed.), Reidel, Dordrecht (1985) 374\u2013383."},{"key":"4_CR20","first-page":"255","volume":"307","author":"L. Caniglia","year":"1988","unstructured":"L. Caniglia, A. Galligo and J. Heintz. \u201cBorne simplement exponentielle pour les degr\u00e9s dans le th\u00e9or\u00e8me des z\u00e9ros sur un corps de caract\u00e9ristique quelconque\u201d, C.R. Acad. Sci. Paris, t. 307 S\u00e9rie I (1988) 255\u2013258.","journal-title":"C.R. Acad. Sci. Paris"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"L. Caniglia, A. Galligo and J. Heintz. \u201cSome new effectivity bounds in computational geometry\u201d. In Proc. AAECC-6, (T. Mora. ed.), Springer LNCS 357 (1989) 131\u2013151.","DOI":"10.1007\/3-540-51083-4_54"},{"key":"4_CR22","unstructured":"J.P. Cardinal. \u201cDualit\u00e9 et algorithmes it\u00e9ratives pour la solution des syst\u00e9mes polynomiaux\u201d. Th\u00e9se, U. de Rennes I (1993)."},{"issue":"No.4","key":"4_CR23","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1142\/S0218196792000244","volume":"2","author":"F. Cucker","year":"1992","unstructured":"F. Cucker, J.L. Monta\u00f1a, L.M. Pardo.\u201cTime Bounded Computations over the reals\u201d. Int. J. of Alg. and Comp., Vol.2, No. 4, (1992) 395\u2013408.","journal-title":"Int. J. of Alg. and Comp."},{"issue":"N.1","key":"4_CR24","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(94)00069-7","volume":"133","author":"F. Cucker","year":"1994","unstructured":"F. Cucker, M. Shub, S. Smale. \u201cSeparation of complexity lasses in Koiran's weak model\u201d. Theor. Comp. Sci. 133, N. 1, (1994) 3\u201315.","journal-title":"Theor. Comp. Sci."},{"key":"4_CR25","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/S0747-7171(88)80004-X","volume":"5","author":"J. Davenport","year":"1988","unstructured":"J. Davenport, J. Heintz. \u201cReal quantifier elimination is doubly exponential\u201d. J. Symbolic Computation 5 (1988) 29\u201335. Reprinted in: Algorithms in Real Algebraic Geometry, ed. by Denis A. Arnon and Bruno Buchberger, Academic Press (1988) 29\u201335.","journal-title":"J. Symbolic Computation"},{"key":"4_CR26","unstructured":"D. Duval.\u201cDiverses Questions Relatives au Cacul Formel avec des Nombres Alg\u00e8briques\u201d. Th\u00e8se d' Etat, Grenoble (1987)."},{"key":"4_CR27","unstructured":"N. Fitchas, M. Giusti and F. Smietanski. \u201cSur la complexit\u00e9 du th\u00e9or\u00e8me des z\u00e9ros\u201d, Manuscript Ecole Polytechnique (1993)."},{"key":"4_CR28","unstructured":"N. Fitchas, A. Galligo, J. Morgenstern. \u201cAlgorithmes rapides en s\u00e9quentiel et en parallele pour l'\u00e9limination de quantificateurs en g\u00e9om\u00e9trie \u00e9l\u00e9mentaire\u201d. Seminaire de Structures Algebriques Ordennes, Universit\u00e9 de Paris VII (1987)."},{"key":"4_CR29","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey, D. Johnson. \u201cComputers and Intractability: A Guide to the Theory of NP-completeness\u201d. Freeman, San Francisco (1979)."},{"issue":"No.4","key":"4_CR30","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1137\/0213050","volume":"13","author":"J. Gathen von zur","year":"1984","unstructured":"J. von zur Gathen. \u201cParallel algorithms for algebraic problems\u201d. SIAM J. Comput., Vol. 13, No. 4 (1984) 802\u2013824","journal-title":"SIAM J. Comput."},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"J.Von zur Gathen.\u201cParallel arithmetic computations: a survey\u201d. In Proc. 13 th Mathematical Foundations on computer Science, (1986) 93\u2013112.","DOI":"10.1007\/BFb0016236"},{"key":"4_CR32","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen. \u201cAlgebraic Complexity Theory\u201d. Annual Review of Computer Science, vol. 3 (1988).","DOI":"10.1146\/annurev.cs.03.060188.001533"},{"key":"4_CR33","volume-title":"Transcendental and Algebraic Numbers","author":"A.O. Gel'fond","year":"1960","unstructured":"A.O. Gel'fond. \u201cTranscendental and Algebraic Numbers\u201d. Dover, NY (1960)."},{"key":"4_CR34","first-page":"247","volume":"356","author":"P. Gianni","year":"1989","unstructured":"P. Gianni, T. Mora. \u201cAlgebraic solution of systems of polynomial equations using Gr\u00f6bner bases\u201d. In Proc. AAECC-5, LNCS 356 (1989) 247\u2013257.","journal-title":"LNCS"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"M. Giusti and J. Heintz. \u201cAlgorithmes-disons rapides-pour la d\u00e9composition d'une vari\u00e9t\u00e9 alg\u00e9brique en composantes irr\u00e9ductibles et \u00e9quidimensionelles\u201d, In Proc. MEGA '90, Birkh\u00e4user Progress in Math. 94, (T. Mora and C. Traverso, eds.) (1991) 169\u2013193.","DOI":"10.1007\/978-1-4612-0441-1_11"},{"key":"4_CR36","unstructured":"M.Giusti and J.Heintz. \u201cLa d\u00e9termination des points isol\u00e9s et de la dimension d'une vari\u00e9t\u00e9 alg\u00e9brique peut se faire en temps polynomial\u201d. In Computational Algebraic Geometry and Commutative Algebra\u201d, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 216\u2013256."},{"key":"4_CR37","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/BF01200407","volume":"3","author":"M. Giusti","year":"1993","unstructured":"M. Giusti, J. Heintz and J. Sabia. \u201cOn the efficiency of effective Nullstellens\u00e4tze\u201d. Computational Complexity 3 (1993) 56\u201395.","journal-title":"Computational Complexity"},{"key":"4_CR38","doi-asserted-by":"crossref","unstructured":"M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo. \u201cWhen polynomial equation systems can be solved\u2019 fast\u2019 ?\u201d. In this volume (1995).","DOI":"10.1007\/3-540-60114-7_16"},{"key":"4_CR39","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0022-4049(91)90097-L","volume":"76","author":"L. G. Vega","year":"1991","unstructured":"L. Gonzalez Vega. \u201cDeterminantal formulae for the solution set of zero-dimensional ideals\u201d. J. of Pure and App. Algebra, 76 (1991) 57\u201380.","journal-title":"J. of Pure and App. Algebra"},{"key":"4_CR40","first-page":"65","volume":"4","author":"D. Y. Grigor'ev","year":"1988","unstructured":"D. Yu. Grigor'ev. \u201cLower Bounds in Algebraic Computational Complexity\u201d. J. of Soviet Mathematics, 4 (1988) 65\u2013108.","journal-title":"J. of Soviet Mathematics"},{"issue":"No.2","key":"4_CR41","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1137\/0406019","volume":"6","author":"P. Gritzmann","year":"1993","unstructured":"P. Gritzmann and B. Sturmfels. \u201cMinkowski Addition of Polytopes: Computational Complexity and Applications to Gr\u00f6bner Bases.\u201d SIAM J. Disc. Math., Vol. 6, No. 2 (1993) 246\u2013269.","journal-title":"SIAM J. Disc. Math."},{"key":"4_CR42","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","volume":"24","author":"J. Heintz","year":"1983","unstructured":"J. Heintz. \u201cDefinability and fast quantifier elimination over algebraically closed fields\u201d. Theor. Comp. Science 24, (1983) 239\u2013278.","journal-title":"Theor. Comp. Science"},{"key":"4_CR43","first-page":"269","volume":"356","author":"J. Heintz","year":"1989","unstructured":"J. Heintz. \u201cOn the computational complexity of polynomials and bilinear mappings\u201d, Proc. AAECC-5, Springer LNCS 356 (1989) 269\u2013300.","journal-title":"Proc. AAECC-5, Springer LNCS"},{"key":"4_CR44","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1090\/dimacs\/006\/08","volume":"6","author":"J. Heintz","year":"1991","unstructured":"J. Heintz, T. Recio and M.F. Roy. \u201cAlgorithms in Real Algebraic Geometry and Applications to Computational Geometry\u201d. DIMACS series in Discrete Math. and Theor. Comp. Sci. 6 (1991) 137\u2013162.","journal-title":"DIMACS series in Discrete Math. and Theor. Comp. Sci."},{"key":"4_CR45","doi-asserted-by":"crossref","first-page":"101","DOI":"10.24033\/bsmf.2138","volume":"118","author":"J. Heintz","year":"1990","unstructured":"J. Heintz, M.-F. Roy and P. Solerno. \u201cSur la Complexit\u00e9 du Principe de Tarski-Seidenberg\u201d. Bull. Soc. Math. de France 118, (1990) 101\u2013126.","journal-title":"Bull. Soc. Math. de France"},{"key":"4_CR46","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1006\/jcom.1993.1031","volume":"9","author":"J. Heintz","year":"1993","unstructured":"J. Heintz and J. Morgenstern. \u201cOn the intrinsic complexity of elimination theory\u201d. J. of Complexity 9 (1993) 471\u2013498.","journal-title":"J. of Complexity"},{"key":"4_CR47","unstructured":"J. Heintz and C.P. Schnorr. \u201cTesting Polynomials wich are easy to compute\u201d. In Logic and Algorithmic (an International Symposium in honour of Ernst Specker), Monographie n. 30 de l'Enseignement Math\u00e9matique (1982) 237\u2013254. A preliminary version appeared in Proc. 12th Ann. ACM Symp. on Computing (1980) 262\u2013268."},{"key":"4_CR48","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0304-3975(80)90019-5","volume":"11","author":"J. Heintz","year":"1980","unstructured":"J. Heintz and M. Sieveking. \u201cLower Bounds for polynomials with algebraic coefficients\u201d, Theoret. Comp. Sci. 11 (1980) 321\u2013330.","journal-title":"Theoret. Comp. Sci."},{"key":"4_CR49","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1007\/BF01206635","volume":"95","author":"G. Hermann","year":"1926","unstructured":"G. Hermann. \u201cDie Frage der endlich vielen Schritte in der Theorie der Polynomideale\u201d. Math. Ann. 95 (1926) 736\u2013788.","journal-title":"Math. Ann."},{"key":"4_CR50","unstructured":"F. Hurtado and M. Noy. \u201cEars of triangulations and Catalan numbers\u201d. To appear in Discrete Mathematics."},{"key":"4_CR51","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"O.H. Ibarra","year":"1983","unstructured":"O.H. Ibarra, S. Moran. \u201cEquivalence of Straight-Line Programs\u201d. J. of the ACM 30 (1983) 217\u2013228.","journal-title":"J. of the ACM"},{"issue":"No.5","key":"4_CR52","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0020-0190(81)90019-3","volume":"12","author":"O.H. Ibarra","year":"1981","unstructured":"O.H. Ibarra, S. Moran, E. Rosier. \u201cProbabilistic algorithms and straight-line programs for some rank decision problems\u201d. Inf. Proc. Letters, Vol. 12, No. 5 (1981) 227\u2013232.","journal-title":"Inf. Proc. Letters"},{"issue":"No.1","key":"4_CR53","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1145\/42267.45069","volume":"35","author":"E. Kaltofen","year":"1988","unstructured":"E. Kaltofen. \u201cGreatest common divisors of polynomials given by straight-line programs\u201d. J. of the ACM, 35 No. 1 (1988) 234\u2013264.","journal-title":"J. of the ACM"},{"key":"4_CR54","unstructured":"D.E. Knuth. \u201cThe Art of Programming (vol. 2): Semi-numerical Algorithms\u201d Addison-Wesley (1981)."},{"key":"4_CR55","first-page":"375","volume":"5","author":"E. Kaltofen","year":"1989","unstructured":"E. Kaltofen. \u201cFactorization of Polynomials given by straight-line programs\u201d. In Randomness in Computation, Advances in Computing Research 5 (1989) 375\u2013412","journal-title":"Randomness in Computation, Advances in Computing Research"},{"key":"4_CR56","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0747-7171(88)80032-4","volume":"5","author":"H. Kobayashi","year":"1988","unstructured":"H. Kobayashi, T. Fujise and A. Furukawa. \u201cSolving systems of algebraic equations equations by general elimination method\u201d. J. Symb. Comp. 5 (1988) 303\u2013320.","journal-title":"J. Symb. Comp."},{"key":"4_CR57","first-page":"963","volume":"1","author":"J. Koll\u00e1r","year":"1988","unstructured":"J. Koll\u00e1r. \u201cSharp Effective Nullstllensatz\u201d, J. of AMS. 1 (1988) 963\u2013975.","journal-title":"J. of AMS."},{"issue":"no.5","key":"4_CR58","first-page":"407","volume":"318","author":"T. Krick","year":"1994","unstructured":"T. Krick, Luis M. Pardo. \u201cUne approche informatique pour l'approximation diophantienne\u201d. Comptes Rendues de l'Acad. des Sci. Paris, t. 318, S\u00e9rie I, no. 5, (1994) 407\u2013412.","journal-title":"Comptes Rendues de l'Acad. des Sci. Paris"},{"key":"4_CR59","doi-asserted-by":"crossref","unstructured":"T. Krick, L.M. Pardo. \u201cA Computational Method for Diophantine Approximation\u201d. To appear in Proc. MEGA'94, Birkh\u00e4usser Verlag, (1995).","DOI":"10.1007\/978-3-0348-9104-2_11"},{"key":"4_CR60","doi-asserted-by":"crossref","first-page":"534","DOI":"10.1145\/321958.321973","volume":"23","author":"H.T. Kung","year":"1976","unstructured":"H.T. Kung. \u201cNew algorithms and lower bounds for the parallel evaluation of certain rational expressions and recurrences\u201d. J. of the ACM, 23, (1976) 534\u2013543.","journal-title":"J. of the ACM"},{"key":"4_CR61","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0304-3975(81)90064-5","volume":"15","author":"D. Lazard","year":"1981","unstructured":"D. Lazard. \u201cR\u00e9solution des syst\u00e8mes d'\u00e9quations alg\u00e9briques\u201d, Theor. Comp. Sci. 15 (1981) 77\u2013110.","journal-title":"Theor. Comp. Sci."},{"key":"4_CR62","unstructured":"D. Lazard. \u201cSystems of Algebraic Equations (Algorithms and Complexity)\u201d. In Computational Algebraic Geometry and Commutative Algebra\u201d, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 216\u2013256."},{"key":"4_CR63","unstructured":"A.K. Lenstra, H.W. Lenstra. \u201cAlgorithms in Number Theory\u201d. In Handbook of Theoretical Computer Science, Elsevier, ch. 12 (1990) 673\u2013715."},{"key":"4_CR64","doi-asserted-by":"crossref","unstructured":"M. Li and P.M.B. Vit\u00e1nyi. \u201cKolmogorov Complexity and its Applications\u201d. In Handbook of Theoretical Computer Science, Elsevier, ch. 4 (1990) 187\u2013254.","DOI":"10.1016\/B978-0-444-88071-0.50009-6"},{"key":"4_CR65","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01398396","volume":"72","author":"D. W. Masser","year":"1971","unstructured":"D. W. Masser and G. W\u00fcstholz. \u201cFields of large transcendence degree generated by values of elliptic functions\u201d, Invent. Math. 72 (1971) 407\u2013463.","journal-title":"Invent. Math."},{"key":"4_CR66","doi-asserted-by":"crossref","unstructured":"G. Matera. \u201cIntegration of multivariate rationals functions given by straight-line programs\u201d. In this volume (1995).","DOI":"10.1007\/3-540-60114-7_27"},{"key":"4_CR67","unstructured":"G. Matera, J.M. Turull. \u201cThe complexity of elimination: upper bounds\u201d. Work in preparation (1995)."},{"key":"4_CR68","unstructured":"E. Mayr. \u201cMembership in Polynomial Ideals over 67-02 Is Exponential Space Complete\u201d."},{"key":"4_CR69","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E. Mayr","year":"1982","unstructured":"E. Mayr and A. Meyer. \u201cThe complexity of the word problem for commutative semigroups\u201c, Advances in Math. 46 (1982) 305\u2013329.","journal-title":"Advances in Math."},{"key":"4_CR70","unstructured":"M. Mignotte. \u201cMath\u00e9matiques pour le Cacul Formel\u201d, Presses Univ. de France (1989)."},{"key":"4_CR71","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01270397","volume":"4","author":"J.L. Monta\u00f1a","year":"1993","unstructured":"J.L. Monta\u00f1a and L.M. Pardo.\u201cLower bounds for Arithmetic Networks\u201d. AAECC 4 (1993) 1\u201324.","journal-title":"AAECC"},{"key":"4_CR72","doi-asserted-by":"crossref","unstructured":"J.L. Monta\u00f1a, J.E. Morais, L.M. Pardo. \u201cLower Bounds for Arithmetic Networks II:Sum of Betti Numbers\u201d.To appear in AAECC 7 (1995).","DOI":"10.1007\/s002000050018"},{"key":"4_CR73","unstructured":"T. Mora, L. Robbiano. \u201cPoints in Affine and Projective Sapces\u201d. In Computational Algebraic Geometry and Commutative Algebra\u201d, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 216\u2013256."},{"issue":"1","key":"4_CR74","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/BF02579205","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"K. Mulmuley. \u201cA fast parallel algorithmn to compute the rank of a matrix over an arbitrary field\u201d. COMBINATORICA, 7(1) (1987) 101\u2013104.","journal-title":"COMBINATORICA"},{"key":"4_CR75","unstructured":"Newton,I. \u201cDe Analysi per Aequationes Infinitas\u201d. (1667)."},{"key":"4_CR76","doi-asserted-by":"crossref","unstructured":"A.M. Ostrowski.\u201cOn two problems in abstract algebra connected with Horner's rule\u201d. In Studies in Math. and Mech. presented to Richard von Mises Academicv Press (1954) 40\u201348.","DOI":"10.1016\/B978-1-4832-3272-0.50010-7"},{"key":"4_CR77","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/BF01446571","volume":"289","author":"P. Philippon","year":"1991","unstructured":"P. Philippon.\u201cSur des hauteurs alternatives, I\u201d. Math. Ann. 289 (1991) 255\u2013283.","journal-title":"Math. Ann."},{"issue":"2","key":"4_CR78","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.5802\/aif.1426","volume":"44","author":"P. Philippon","year":"1994","unstructured":"P. Philippon. \u201cSur des hauteurs alternatives, II\u201d. Ann. Inst. Fourier, Grenoble 44, 2 (1994) 1043\u20131065.","journal-title":"Ann. Inst. Fourier, Grenoble"},{"key":"4_CR79","unstructured":"P. Philippon.\u201cSur des hauteurs alternatives, III\u201d. To appear in J. Math. Pures Appl."},{"key":"4_CR80","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/S0022-0000(77)80013-5","volume":"14","author":"D.A. Plaisted","year":"1977","unstructured":"D.A. Plaisted.\u201cSparse Complex Polynomials and Polynomial Reducibility\u201d. J. of Comput. Syst. Sci. 14 (1977) 210\u2013221.","journal-title":"J. of Comput. Syst. Sci."},{"key":"4_CR81","first-page":"573","volume":"316","author":"R. Pollack","year":"1991","unstructured":"R. Pollack, M.F. Roy. \u201cOn the number of cells defined by a set of polynomials\u201d. C.R. Acad. Sci. Paris 316 (1991) 573\u2013577.","journal-title":"C.R. Acad. Sci. Paris"},{"key":"4_CR82","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/0885-064X(87)90022-7","volume":"3","author":"J. Renegar","year":"1987","unstructured":"J. Renegar. \u201cOn the Worst-Case Arithmetic Complexity of Approximating Zeros of Polynomials\u201d. J. of Complexity 3 (1987) 90\u2013113","journal-title":"J. of Complexity"},{"key":"4_CR83","doi-asserted-by":"crossref","unstructured":"H. Riesel. \u201cPrime Numbers and Computer Methods for Factorization\u201d. Birkh\u00e4user Progress in Math. 57 (1985).","DOI":"10.1007\/978-1-4757-1089-2"},{"key":"4_CR84","unstructured":"J. Sabia and P. Solern\u00f3. \u201cBounds for traces in complete intersections and degrees in the Nullstellensatz\u201d. To appear in AAECC Journal (1993)."},{"key":"4_CR85","unstructured":"F. Santos. \u201cGeometri\u00e1 Combinatoria de Curvas Algebraicas y Diagramas de Delaunay en el piano\u201d. Tesis, U. de Cantabria (1995)."},{"key":"4_CR86","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"J.T. Schwartz. \u201cFast Probabilistic Algorithms for Verification of Polynomial Identities\u201d. J. of the ACM 27, (1980), 701\u2013717.","journal-title":"J. of the ACM"},{"key":"4_CR87","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-94694-3","volume-title":"Einf\u00fchrung in die transzendenten Zahlen","author":"T. Schneider","year":"1957","unstructured":"T. Schneider. \u201cEinf\u00fchrung in die transzendenten Zahlen\u201d. Springer-Verlag, Berlin (1957)."},{"key":"4_CR88","unstructured":"A. Schonhage, A. F.W. Grotefeld, E. Vetter. \u201cFast Algorithms (A Multitape Turing machine Implementation)\u201d. B. I. Wissenschaftverlag (1994)."},{"issue":"No.2","key":"4_CR89","first-page":"459","volume":"6","author":"M. Shub","year":"1993","unstructured":"M. Shub, S. Smale. \u201cComplexity of B\u00e9zout's theorem I: Geometric aspects\u201d. J. Am. Math. Soc., Vol. 6, No. 2 (1993) 459\u2013501","journal-title":"J. Am. Math. Soc."},{"key":"4_CR90","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(94)90122-8","volume":"133","author":"M. Shub","year":"1994","unstructured":"M. Shub, S. Smale. \u201cComplexity of B\u00e9zout's theorem V: Polynomial time\u201d. Theor. Comp. Sci., 133 (1994) 141\u2013164","journal-title":"Theor. Comp. Sci."},{"key":"4_CR91","unstructured":"M. Shub, S.Smale. \u201cOn the Intractability of Hilbert's Nullstellensatz and an algebraic version of \u201cNP=P ?\u201d. Preprint of IBM Research Division RC 19624 6\/23\/94 (1994)."},{"key":"4_CR92","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0885-064X(87)90021-5","volume":"3","author":"S. Smale","year":"1987","unstructured":"S. Smale. \u201cOn the Topology of Algorithms, I\u201d. J. of Complexity, 3 (1987) 81\u201389.","journal-title":"J. of Complexity"},{"issue":"N.2","key":"4_CR93","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/S0273-0979-1985-15391-1","volume":"13","author":"S. Smale","year":"1985","unstructured":"S. Smale.\u201cOn the Efficiency of Algorithms of Analysis\u201d. Bull of the AMS 13, N. 2 (1985) 87\u2013121.","journal-title":"Bull of the AMS"},{"key":"4_CR94","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BF00289512","volume":"1","author":"V. Strassen","year":"1972","unstructured":"V. Strassen. \u201cBerechnung und Programm I\u201d. Acta Inform., 1 (1972) 320\u2013334.","journal-title":"Acta Inform."},{"key":"4_CR95","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0203010","volume":"3","author":"V. Strassen","year":"1974","unstructured":"V. Strassen. \u201cPolynomials with rational coefficients which are hard to compute\u201d, SIAM J. Comput. 3 (1974) 128\u2013149.","journal-title":"SIAM J. Comput."},{"key":"4_CR96","first-page":"184","volume":"264","author":"V. Strassen","year":"1973","unstructured":"V. Strassen. \u201cVermeidung von Divisionen\u201d, Crelle J. Reine Angew. Math. 264 (1973) 184\u2013202.","journal-title":"Crelle J. Reine Angew. Math."},{"key":"4_CR97","unstructured":"V. Strassen. \u201cAlgebraic Complexity Theory\u201d. In Handbook of Theoretical Computer Science, Elsevier, ch. 11 (1990) 634\u2013671."},{"issue":"No.1","key":"4_CR98","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1137\/0401014","volume":"1","author":"B. Sturmfels","year":"1988","unstructured":"B. Sturmfels. \u201cSome Applications of Affine Gale Diagrams to Polytopes with Few Vertices.\u201d SIAM J. Disc. Math., Vol. 1, No. 1 (1988) 121\u2013133","journal-title":"SIAM J. Disc. Math."},{"key":"4_CR99","unstructured":"B. Sturmfels. \u201cSparse Elimination Theory\u201d. In Computational Algebraic Geometry and Commutative Algebra\u201d, Proc. of the Cortona Conf. on Comp. Algebraic Geometry and Commutative Algebra, D. Eisenbud and L. Robbiano (eds.). Symposia Matematica, vol. XXXIV, Istituto Nazionale di Alta Matematica, Cambridge University Press (1993) 264\u2013298."},{"key":"4_CR100","doi-asserted-by":"crossref","first-page":"249","DOI":"10.2748\/tmj\/1178227496","volume":"43","author":"B. Sturmfels","year":"1991","unstructured":"B. Sturmfels. \u201cGr\u00f6bner Bases of Toric Varieties.\u201d Tohoku Math. J., 43 (1991) 249\u2013261.","journal-title":"Tohoku Math. J."},{"issue":"No.3","key":"4_CR101","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1145\/322326.322342","volume":"29","author":"A. C. Yao","year":"1982","unstructured":"A. C.C. Yao. \u201cOn Paralell Computation for the Knapsack problem\u201d. J. of the ACM, vol. 29, No. 3 (1982) 898\u2013903.","journal-title":"J. of the ACM"},{"key":"4_CR102","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0747-7171(08)80018-1","volume":"9","author":"R. Zippel","year":"1990","unstructured":"R. Zippel. \u201cInterpolating Polynomials from their Values\u201d. J. Symbol. Comput., 9 (1990) 375\u2013403","journal-title":"J. Symbol. Comput."}],"container-title":["Lecture Notes in Computer Science","Applied Algebra, Algebraic Algorithms and Error-Correcting Codes"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60114-7_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,31]],"date-time":"2021-12-31T09:26:04Z","timestamp":1640942764000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60114-7_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601142","9783540494409"],"references-count":102,"URL":"https:\/\/doi.org\/10.1007\/3-540-60114-7_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}