Registro:

Referencias:

• Abrahamson, K., Time-space tradeoffs for algebraic problems on general sequential machines (1991) J. Comput. System. Sci., 43, pp. 269-289
• Baur, W., Simplified lower bounds for polynomials with algebraic coefficients (1997) J. Complexity, 13, pp. 38-41
• Beame, P., A general sequential time-space tradeoff for finding unique elements (1991) SIAM J. Comput., 20, pp. 270-277
• Ben-Or, M., Cleve, R., Computing algebraic formulas using a constant number of registers (1992) SIAM J. Comput., 21, pp. 54-58
• Bochnak, J., Coste, M., Roy, M.-F., Géométrie Algébrique Réelle (1987) Ergebnisse der Mathematik und Iher Grenzgebiete, , New York/Berlin: Springer-Verlag
• Borodin, A., Time-space tradeoffs (getting closer to the barrier?) (1993) Algorithms and Computation, Proc. of the 4th ACM-SIGSAM Int. Symp. ISAAC'93, 762, pp. 209-220. , K. W. Ny. Lecture Notes in Computer Science. New York/Berlin: Springer-Verlag
• Borodin, A., Cook, S., A time-space tradeoff for sorting on a general sequential model of computation (1982) SIAM J. Comput., 11, pp. 287-297
• Borodin, A., Fich, F., Meyer Auf Der Heide, F., Upfal, E., Wigderson, A., A time-space tradeoff for element distinctness (1987) SIAM J. Comput., 16, pp. 97-99
• Borodin, A., Fischer, M.J., Kirkpatrick, D.G., Lynch, N.A., Tompa, M., A time-space tradeoff for sorting on non-oblivious machines (1981) J. Comput. System Sci., 22, pp. 351-364
• Borodin, A., Munro, I., (1975) The Computational Complexity of Algebraic and Numeric Problems, , Amsterdam: Elsevier
• Brownawell, D.W., Bounds for the degree in the Nullstellensatz (1987) Ann. of Math., 126, pp. 577-591
• Bürgisser, P., Clausen, M., Shokrollahi, M.A., Algebraic Complexity Theory (1997) Comprehensive Studies in Mathematics, 315. , New York/Berlin: Springer-Verlag
• Caniglia, L., Galligo, A., Heintz, J., Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque (1988) C. R. Acad. Sci. Paris Sér. I Math., 307, pp. 255-258
• Caniglia, L., Galligo, A., Heintz, J., Some new effectivity bounds in computational geometry (1989) Proceedings 6th International Symposium AAECC-6, 357, pp. 131-152. , T. Mora. Lecture Notes in Computer Science. New York/Berlin: Springer-Verlag
• Chandrasekharan, K., Introduction to Analytic Number Theory (1968) Grundlehren der Math. Wissenschaften, , New York/Berlin: Springer-Verlag
• Duris, P., Galil, Z., A time-space tradeoff for language recognition (1981) In Proceedings of the 22nd Annual IEEE Symposium on Foundations of Computer Science, pp. 53-57
• Fitchas, N., Galligo, A., Nullstellensatz effectif et Conjecture de Serre (théorème de Quillen-Suslin) pour le calcul formel (1990) Math. Nachr., 149, pp. 231-253
• Fulton, W., Intersection Theory (1984) Ergebnisse der Mathematik und Iher Grenzgebiete, 24. , New York/Berlin: Springer-Verlag
• Von Zur Gathen, J., (1993) Parallel Linear Algebra, pp. 573-617. , San Mateo: Morgan Kaufmann
• Von Zur Gathen, J., Strassen, V., Some polynomials which are hard to compute (1980) Theoret. Comput. Sci., 11, pp. 331-335
• 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., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1997) 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 11th International Symposium AAECC-11, 948, pp. 205-231. , G. Cohen, M. Giusti, & T. Mora. Lecture Notes in Computer Science. New York/Berlin: Springer-Verlag
• Grigor'Ev, D.yu., An application of separability and independence notions for proving lower bounds of circuit complexity (1976) Notes of Scientific Seminars of LOMI 60
• Heintz, J., Fast quantifier elimination over algebraically closed fields (1983) Theoret. Comput. Sci., 24, pp. 239-277
• Heintz, J., On the computational complexity of polynomials and bilinear mappings: A survey (1989) Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-5, 356, pp. 269-300. , L. Huget, & A. Poli. Lecture Notes in Computer Science. New York/Berlin: Springer-Verlag
• Heintz, J., Morgenstern, J., On the intrinsic complexity of elimination theory (1993) J. Complexity, 9, pp. 471-498
• Heintz, J., Roy, M.-F., Solernó, P., Sur la complexité du principe de Tarski-Seidenberg (1990) Bull. Soc. Math. France, 118, pp. 101-126
• Heintz, J., Schnorr, C.P., Testing polynomials which are easy to compute (1982) In Proceedings 12th Annual ACM Symposium on Theory of Computing, pp. 262-268
• Heintz, J., Sieveking, M., Lower bounds for polynomials with algebraic coefficients (1980) Theoret. Comput. Sci., 11, pp. 321-330
• Ja'Ja', J., Time-space tradeoffs for some algebraic problems (1983) J. Assoc. Comput. Math., 30, pp. 657-667
• Kollár, J., Sharp effective Nullstellensatz (1988) J. Amer. Math. Soc., 1, pp. 963-975
• Krick, T., Sabia, J., Solernó, P., On intrinsic bounds in the Nullstellensatz (1997) Appl. Algebra Engrg. Comm. Comput., 8, pp. 125-134
• Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) In Proceedings MEGA'94 Algorithms in Algebraic Geometry and Applications, pp. 193-254. , (L. González-Vega and T. Recio, Eds.)
• Lengauer, T., Tarjan, R.E., Upper and lower bounds on time-space tradeoffs (1979) In Proceedings 11th Annual ACM Symposium on Theory of Computing, pp. 262-277
• Lickteig, T.M., On Semialgebraic Decision Complexity (1990) Habilitationsschrift, Universität Tübingen TR-90-052, , Berkeley: Int. Comp. Sc. Inst
• Lickteig, T.M., Werther, K., How can a complex square root be computed in an optimal way? (1995) Comput. Complexity, 5, pp. 222-236
• Michaux, C., Une remarque à propos des machines sur R introduites par Blum, Shub et Smale (1989) C. R. Acad. Sci. Paris Sér. I Math., 309, pp. 435-437
• Montaña, J.L., Pardo, L.M., Lower bounds for arithmetic networks (1993) Appl. Algebra Engrg. Comm. Comput., 4, pp. 1-24
• Pardo, L.M., How lower and upper complexity bounds meet in elimination theory (1995) Proceedings 11th International Symposium AAECC-11, 948, pp. 33-69. , G. Cohen, M. Giusti, & T. Mora. Lecture Notes in Computer Science. New York/Berlin: Springer-Verlag
• Paterson, M.S., Stockmeyer, L.J., On the number of nonscalar multiplications necessary to evaluate polynomials (1973) SIAM J. Comput., 2, pp. 60-66
• Paul, W.J., Tarjan, R.E., Time-space tradeoffs in a pebble game (1978) Acta Inform., 10, pp. 111-115
• Philippon, P., (1989) Théorème des Zéros Effectif, , d'après J. Kollár, Publications de l'Université Pierre et Marie Curie, Paris VI, 88, Groupe d'étude sur les Problèmes diophentiens 1988-1989, Exposé
• Pippenger, N., A time-space tradeoff (1978) J. Assoc. Comput. Match., 25, pp. 509-515
• Pippenger, N., Pebbling (1980) In, Proceedings 5th IBM Symposium on Mathematical Foundations on Computer Science
• Savage, J.E., Space-time tradeoffs for banded matrix problems (1984) J. Assoc. Comput. Mach., 31, pp. 422-437
• Savage, J.E., Swamy, S., Space-time tradeoffs on the FFT algorithm (1978) IEEE Trans. Inform. Theory, 24, pp. 563-568
• Savage, J.E., Swamy, S., Space-time Tradeoffs for Oblivious Integer Multiplication (1979) Lecture Notes in Computer Science, 71. , New York/Berlin: Springer-Verlag. p. 240-251
• J. E. Savage, Space-time tradeoffs - A survey (1981) In, Proceedings 3rd Hungarian Computer Science Conference
• 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
• Shafarevich, I.R., (1994) Basic Algebraic Geometry I: Varieties in Projective Space, , New York/Berlin: Springer-Verlag
• Sombra, M., Bounds for the Hilbert function of polynomials ideals and for the degrees in the Nullstellensatz (1997) J. Pure Appl. Algebra, 117-118, pp. 565-599
• Stoss, H.J., Lower bounds for the complexity of polynomials (1989) Theoret. Comput. Sci., 64, pp. 15-23
• Stoss, H.J., On the representation of rational functions of bounded complexity (1989) Theoret. Comput. Sci., 64, pp. 1-13
• Strassen, V., Polynomials with rational coefficients which are hard to compute (1974) SIAM J. Comput., 3, pp. 128-149
• Strassen, V., Algebraic complexity (1990) Handbook of Theoretical Computer Science, , Amsterdam: Elsevier. p. 634-672
• Tompa, M., Time-space tradeoffs for computing functions using conectivity of their circuits (1980) J. Comput. System Sci., 20, pp. 118-132
• P. M. Vaidya, Space-time tradeoffs for orthogonal range queries (1985) In Proceedings 17th Annual ACM Symposium on Theory of Computing, pp. 169-174
• Vorobjov, N., Bounds of real roots of a system of algebraic equations (1984) Notes of Scientific Seminars 137
• Van Der Waerden, B.L., Algebra I (1960) Auflage der Modernen Algebra, , New York/Berlin: Springer-Verlag
• Yao, A.C., Space-time tradeoff for answering range queries (1982) In Proceedings 14th Annual ACM Symposium on Theory of Computing, pp. 128-136
• Yao, A.C., Near optimal time-space tradeoff for element distinctness (1988) In Proceedings 29nd Annual IEEE Symposium on Foundations of Computer Science, pp. 183-187
• Yesha, Y., Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any sequential random access computer (1984) J. Comput. System Sci., 29, pp. 183-197

Citas:

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

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

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

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