Registro:

Referencias:

• Aldaz, M., Heintz, J., Matera, G., Montaña, J.L., Pardo, L.M., Combinatorial hardness proofs for polynomial evaluation (1998) Lecture Notes in Computer Science, 1450, pp. 67-175. , in Proceedings 23rd International Symposium on Mathematical Foundations of Computer Science, MFoCS'98, (L. Brim et al., eds.); Springer-Verlag, Berlin
• Aldaz, M., Matera, G., Montaña, J.L., Pardo, L.M., A new method to obtain lower bounds for polynomial evaluation (2001) Theoret. Comput. Sci., 259 (1-2), pp. 577-596
• Alder, A., Grenzrang und Grenzkomplexität aus algebraischer und topologischer Sicht (1984), PhD thesis, Universität Zürich, Philosophische Fakultät II; Atiyah, M.F., MacDonald, J.G., (1969) Introduction to Commutative Algebra, , Addison-Wesley, Reading, MA
• Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real equation solving: The hypersurface case (1997) J. Complexity, 13 (1), pp. 5-27
• Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Math. Z., 238 (1), pp. 115-144
• Bayer, D., Mumford, D., What can be computed in algebraic geometry? (1993) Symposia Matematica, 34, pp. 1-49. , in Computational Algebraic Geometry and Commutative Algebra, (D. Eisenbud and L. Robbiano, eds.); Cambridge; Instituto Nazionale di Alta Matematica, Cambridge University Press, Cambridge
• Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , Springer-Verlag, New York
• Borel, E., La définition en mathématiques (1948) Les Grands Courants de la Pensée Mathématique, pp. 24-34. , Cahiers du Sud, Paris
• Borodin, A., Time space tradeoffs (getting closer to the barriers?) (1993) 4th International Symposium on Algorithms and Computation, ISAAC '93, Hong Kong, December 15-17, 1993, Lecture Notes in Computer Science, 762, pp. 209-220. , Springer-Verlag, Berlin
• Bruno, N., Heintz, J., Matera, G., Wachenchauzer, R., Functional programming concepts and straight-line programs in computer algebra (2002) Math. Comput. Simulation, 60 (6), pp. 423-473
• Bürgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic complexity theory (1997) Grundlehren der Mathematischen Wissenschaften, 315. , Springer-Verlag, Berlin
• Caniglia, L., Galligo, A., Heintz, J., Some new effectivity bounds in computational geometry (1989) Proceedings of AAECC-6, Lecture Notes in Computer Science, 357, pp. 131-152. , in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, (T. Mora et al., eds.); Springer-Verlag, Berlin
• Canny, J., Some algebraic and geometric problems in PSPACE (1988) Proceedings 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, 2-4 May 1988, pp. 460-467. , ACM Press, New York
• Castaño, B., Heintz, J., Llovet, J., Martínez, R., On the data structure straight-line program and its implementation in symbolic computation (2001) Math. Comput. Simulation, 51, pp. 497-528
• Castro, D., Hägele, K., Morais, J.E., Pardo, L.M., Kronecker's and Newton's approaches to solving: A first comparison (2001) J. Complexity, 17 (1), pp. 212-303
• Castro, D., Montaña, J.L., Pardo, L.M., San Martin, J., The distribution of condition numbers of rational data of bounded bit length (2002) Found. Comput. Math., 2 (1), pp. 1-52
• Chistov, A.L., Grigoriev, D.Y., Subexponential time solving systems of algebraic equations (1983), I, II. LOMI preprints E-9-83, E-10-83, Steklov Institute, Leningrad; Cucker, F., Smale, S., Complexity estimates depending on condition and round-off error (1999) J. Assoc. Comput. Mach., 46 (1), pp. 113-184
• Davenport, J.H., Heintz, J., Real quantifier elimination is doubly exponential (1988) J. Symbolic Comput., 5, pp. 29-35
• Dickenstein, A., Fitchas, N., Giusti, M., Sessa, C., The membership problem for unmixed polynomial ideals is solvable in single exponential time (1991) Discrete Appl. Math., 33, pp. 73-94
• Fitchas, N., Galligo, A., Morgenstern, J., Algorithmes rapides en sequentiel et en parallele pour l'élimination des quantificateurs en Géométrie élementaire (1990) Pub. Math. Univ. Paris VII, 32, pp. 103-145. , in Seminaire sur les structures algébriques ordonnés (F. Delon, M. Dickmann, and D. Gondard, eds.); Paris
• Fitchas, N., Galligo, A., Morgenstern, J., Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields (1990) J. Pure Appl. Algebra, 67 (1), pp. 1-14
• Fitchas, N., Giusti, M., Smietanski, F., Sur la complexité du théorème des zéros (1995) Proceedings 2nd International Conference on Non-Linear Optimization and Approximation, Approximation and Optimization, 8, pp. 247-329. , in Approximation and Optimization in the Caribbean II, (J. Guddat et al., ed.); Peter Lange Verlag, Frankfurt am Main
• Fulton, W., (1984) Intersection Theory, , Springer-Verlag, Berlin
• Gelfand, I.M., Kapranov, M.M., Zelevinsky, A.V., (1994) Discriminants, Resultants, and Multidimensional Determinants, , Birkhäuser, Boston
• Gianni, P., Mora, T., Algebraic solution of systems of polynomial equations using Gröbner bases (1989) Proceedings of AAECC-5, Menorca, Spain, June 15-19, 1987, Lecture Notes in Computer Science, 356, pp. 247-257. , in Proceedings 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, (L. Huguet and A. Poli, eds.); Springer-Verlag, Berlin
• Giusti, M., Hägele, K., Heintz, J., Morais, J.E., Montaña, J.L., Pardo, L.M., Lower bounds for diophantine approximation (1997) J. Pure Appl. Algebra, 117-118, pp. 277-317
• Giusti, M., Heintz, J., Algorithmes-disons rapides-pour la décomposition d' une variété algébrique en composantes irréductibles et équidimensionelles (1991) Proceedings of MEGA '90, Progress in Mathematics, 94, pp. 169-194. , Effective Methods in Algebraic Geometry (T. Mora and C. Traverso, eds.); Birkhäuser, Basel
• Giusti, M., Heintz, J., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Symposia Matematica, 34, pp. 216-256. , in Computational Algebraic Geometry and Commutative Algebra, (D. Eisenbud and L. Robbiano, eds.); Cambridge University Press, Cambridge
• Giusti, M., Heintz, J., Kronecker's smart, little black-boxes (2001) FoCM'99, Oxford 1999, London Mathematical Society Lecture Notes Series, 284, pp. 69-104. , in Proceedings of Foundations of Computational Mathematics, (A. Iserles, R. Devore, and E. Süli, eds.); Cambridge University Press, Cambridge
• Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure Appl. Algebra, 124, pp. 101-146
• Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., When polynomial equation systems can be solved fast? (1995) Proceedings AAECC-11, Lecture Notes in Computer Science, 948, pp. 205-231. , in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, (G. Cohen, H. Giusti, and T. Mora, eds.); Springer-Verlag, Berlin
• Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., Le rôle des structures de données dans les problèmes d'élimination (1997) C. R. Acad. Sci. Paris, 325, pp. 1223-1228
• Giusti, M., Heintz, J., Sabia, J., On the efficiency of effective nullstellensätze (1993) Comput. Complexity, 3, pp. 56-95
• Giusti, M., Lecerf, G., Salvy, B., A gröbner-free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
• Giusti, M., Schost, E., Solving some over-determined systems (1999) ISSAC'99, July 28-31, 1999, Vancouver, Canada, pp. 1-8. , in Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, (S. Dooley, ed.); ACM Press, New York
• Goldberg, P., Jerrum, M., Bounding the vapnik-chervonenkis dimension of concept classes parametrized by real numbers (1995) Machine Learning, 18, pp. 131-148
• Grigoriev, D., Vorobjov Jr., N.N., Solving systems of polynomial inequalities in sub-exponential time (1988) J. Symbolic Comput., 5 (1-2), pp. 37-64
• Hägele, K., Morais, J.E., Pardo, L.M., Sombra, M., On the intrinsic complexity of the arithmetic nullstellensatz (2000) J. Pure Appl. Algebra, 146 (2), pp. 103-183
• Heintz, J., Definability bounds of first-order theories of algebraically closed fields (1979) FCT'79, pp. 160-166. , (Extended abstract), in Proceedings of Fundamentals of Computation Theory, (L. Budach, ed.); Berlin/Wendisch-Rietz, 1979; Akademie Verlag, Berlin
• Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277
• Heintz, J., On the computational complexity of polynomials and bilinear mappings (1989) Proceedings of AAECC-5, Menorca, Spain, June 15-19, 1987, Lecture Notes in Computer Science, 356, pp. 269-300. , A survey in Proceedings 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (L. Huguet and A. Poli, eds.); Springer-Verlag, Berlin
• Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complexity, 16 (1), pp. 70-109
• Heintz, J., Matera, G., Pardo, L.M., Wachenchauzer, R., The intrinsic complexity of parametric elimination methods (1998) Electron. J. SADIO, 1 (1), pp. 37-51
• Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Engng. Commun. Comput., 11 (4), pp. 239-296
• Heintz, J., Roy, M.-F., Solernó, P., On the complexity of semialgebraic sets (1989) Proceedings of the IFIP 11th World Computer Congress, San Francisco, USA, August 28-September 1, 1989, pp. 293-298. , in Information Processing 89, (G. Ritter, ed.); North-Holland/IFIP, Amsterdam
• Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bull. Soc. Math. France, 118 (1), pp. 101-126
• Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute (1982) International Symposium on Logic and Algorithmic, Zurich 1980, Monographie de l'Enseignement Mathématique, 30, pp. 237-254
• Heintz, J., Sieveking, M., Absolute primality of polynomials is decidable in random polynomial-time in the number of variables (1981) Lecture Notes in Computer Science, 115, pp. 16-28. , in ICALP 81: Proceedings 8th International Colloquium on Automata, Languages and Programming, Acre (Akko), Israel July 13-17, 1981, (Shimon Even and Oded Kariv, eds.); Springer-Verlag, Berlin
• Ierardi, D., Quantifier elimination in the theory of an algebraically closed field (1989) Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Seattle, Washington, 15-17 May 1989, pp. 138-147. , ACM Press, New York
• Iversen, B., Generic local structure of the morphisms in cummutative algebra (1973) Lecture Notes in Mathematics, 310. , Springer-Verlag, Berlin
• Jerónimo, G., Sabia, J., On the number of sets definable by polynomials (2000) J. Algebra, 227 (2), pp. 633-644
• Kaltofen, E., Greatest common divisors of polynomials given by straight-line programs (1988) J. Assoc. Comput. Mach., 35 (1), pp. 231-264
• Kollár, J., (1999) Rational Curves on Algebraic Varieties, , Springer-Verlag, New York
• Krick, T., Pardo, L.M., Une approche informatique pour l'approximation diophantienne (1994) C. R. Acad. Sci. Paris, 318 (1), pp. 407-412
• Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) Proceedings of MEGA'94, Progress in Mathematics, 143, pp. 193-254. , in Algorithms in Algebraic Geometry and Applications, (L. González-Vega and T. Recio, eds.); Birkhäuser, Basel
• Kronecker, L., Grundzüge einer arithmetischen Theorie der algebraischen Grössen (1882) J. Reine Angew. Math., 92, pp. 1-122
• Lang, S., (1958) Introduction to Algebraic Geometry, , Interscience, New York
• Lang, S., (1993) Algebra, 3rd Ed., , Addison-Wesley, Reading, MA
• Lecerf, G., (2000) Kronecker 0.16beta-2. Reference Manual, , http://kronecker.medicis.polytechnique.fr/, Laboratoire GAGE, École Polytechnique, Palaiseau, France
• Lecerf, G., Quadratic Newton iteration for systems with multiplicity (2002) Found. Comput. Math., 2 (3), pp. 247-293
• Li, M., Vitányi, P., (1993) Introduction to Kolmogorov Complexity and Its Applications, , Springer-Verlag, Berlin
• Matera, G., Probabilistic algorithms for geometric elimination (1999) Appl. Algebra Engrg. Commun. Comput., 9 (6), pp. 463-520
• Matsumura, H., (1980) Commutative Algebra, , Benjamin, New York
• Montaña, J.L., Pardo, L.M., Lower bounds for arithmetic networks (1993) Appl. Algebra Engrg. Commun. Comput., 4 (1), pp. 1-24
• Mourrain, B., Pan, V., Solving special polynomial systems by using structural matrices and algebraic residues (1997) Proceedings Foundations of Computational Mathematics (FOCM'97), pp. 287-304. , (F. Crucker and M. Shub, eds.); Springer-Verlag, Berlin
• Mumford, D., The red book of varieties and schemes (1988) Lecture Notes in Mathematics, 1358. , 1st edn., Springer-Verlag, Berlin
• Pardo, L.M., How lower and upper complexity bounds meet in elimination theory (1995) Proceedings of AAECC-11, Lecture Notes in Computer Science, 948, pp. 33-69. , in Applied Algebra, Algebraic Algorithms and Error Correcting Codes, (G. Cohen, H. Giusti, and T. Mora, eds.); Springer-Verlag, Berlin
• Paterson, M., Stockmeyer, L.J., On the number of nonscalar multiplications necessary to evaluate polynomials (1973) SIAM J. Comput., 2 (1), pp. 60-66
• Puddu, S., Sabia, J., An effective algorithm for quantifier elimination over algebraically closed fields using straight-line programs (1998) J. Pure Appl. Algebra, 129 (2), pp. 173-200
• Renegar, J., On the computational complexity and geometry of the first-order theory of the reals. Part I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals (1992) J. Symbol. Comput., 13 (3), pp. 255-300
• Rojas, J.M., Computing complex dimension faster and deterministically (2000), (extended abstract), preprint arXiv:math.AG/0005028; Schnorr, C.P., Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials (1978) Theoret. Comput. Sci., 7, pp. 251-261
• Schönhage, A., An elementary proof for strassen's degree bound (1976) Theoret. Comput. Sci., 3, pp. 267-272
• Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Engrg. Commun. Comput., 13 (5), pp. 349-393
• Shafarevich, I.R., (1994) Basic Algebraic Geometry, , Springer-Verlag
• Shub, M., Smale, S., Complexity of Bézout's theorem I: Geometric aspects (1993) J. Amer. Math. Soc., 6 (2), pp. 459-501
• Shub, M., Smale, S., Complexity of Bézout's theorem II: Volumes and probabilities (1993) Progress in Mathematics, 109, pp. 267-285. , in Computational Algebraic Geometry, (F. Eyssette and A. Galligo, eds.); Birkhäuser, Basel
• Shub, M., Smale, S., Complexity of Bézout's theorem III: Condition number and packing (1993) J. Complexity, 9, pp. 4-14
• Shub, M., Smale, S., Complexity of Bézout's theorem V: Polynomial time (1994) Theoret. Comput. Sci., 133, pp. 141-164
• Shub, M., Smale, S., Complexity of Bézout's theorem IV: Probability of success (1996) SIAM J. Numer. Anal., 33, pp. 141-164
• Strassen, V., Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationspolynomen (1973) Numer. Math., 2, pp. 238-251
• Strassen, V., Vermeidung von Divisionen (1973) Crelle J. Reine Angew. Math., 264, pp. 182-202
• Vapnik, V.N., The nature of statistical learning theory Statistics for Engineering and Information Science, 2nd Ed., , Springer-Verlag, New York, 2000
• Vogel, W., (1984) Results on Bezout's Theorem, , Tata Institute of Fundamental Research, Springer-Verlag, New York
• Von Zur Gathen, J., Parallel arithmetic computations: A survey (1986) Lecture Notes in Computer Science, 233, pp. 93-112. , in Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, Bratislava, Czechoslovakia, August 25-29, 1996, (B. Rovan J. Gruska and J. Wiedermann, eds.); Springer-Verlag, Berlin
• Von Zur Gathen, J., Parallel linear algebra (1993) Synthesis of Parallel Algorithms, , (John H. Reif, ed.), Morgan Kaufmann, Los Altas, CA
• Weispfening, V., The complexity of linear problems in fields (1988) J. Symbolic Comput., 5, pp. 3-27
• Zariski, O., Theory and applications of holomorphic functions on algebraic varieties over arbitrary ground fields (1951) Mem. Amer. Math. Soc., 5, pp. 1-90

Citas:

---------- APA ----------

---------- CHICAGO ----------

---------- MLA ----------

---------- VANCOUVER ----------