The Project TERA

References

1
M. Aldaz, J. Heintz, G. Matera, J. L. Montaña &L.M. Pardo, Time-space tradeoffs in polynomial evaluation procedures. Preprint, 1996.

2
B. Bank, M. Giusti, J. Heintz &G. Mbakop, Polar Varieties, Real Equation Solving and Data-Structures : The Hypersurface Case. To appear in J. of Complexity, 1996.

3
D. Bayer, M. Stillmann , On the complexity of computing syzygies. J. Symbol.Comput. 6, 1988,135-147,

4
S.J. Berkowitz, On computing the determinant in small parallel time using a small number of processors. Inf. Proc. Letters 18, 1984, 147-150.

5
L. Blum, F. Cucker, M. Shub, &S. Smale, Algebraic settings for the Problem "PNP. To appear in Lectures In Applied Mathematics, 1996.

6
A. Borodin, On relating time and space to size and depth. SIAM J. Comput. 6, 1977, 733-744.

7
L. Caniglia, A. Galligo and J. Heintz, Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque. C.R. Acad. Sci. Paris, Série I, Math. 307, 1988, 255-258.

8
L. Caniglia, A. Galligo and J. Heintz, Some new effectivity bounds in computational geometry. In Proc. AAECC-6, ed. T. Mora, Lecture Notes in Computer Science 357, Springer Verlag, 1989, 131-152.

9
J. Canny, Some algebraic and geometric computations in PSPACE. In Proc. 20th Ann. ACM STOC'88, 1988, 46-467.

10
J. Canny &I. Z. Emiris, Efficient algorithms for the sparse resultant and the mixed volume, Preprint (1993).

11
J. Canny &A. Rege, A Toolkit for Algebra and Geometry. Preprint, 1995.

12
A.L. Chistov &D. Yu. Grigor'ev, Subexponential-time solving systems of algebraic equations, LOMI Preprints E-g-83, E-10-83, Leningrad (1983).

13
J.H. Davenport &J. Heintz, Real quantifier elimination is doubly exponential. J. Symbolic Computation 5, 1988, 29 - 35.

14
M. Demazure, Le Theoreme de Complexite de Mayr-Meyer, Notes Informelles de Calcul Formel IV, Ecole Polytechnique (1985).

15
A. Dickenstein, N. Fitchas, M. Giusti, C. Sessa, The membership problem for unmixed polynomial ideals is solvable in single exponential time. Discrete Appl. Math. 33, 1991, 73-94, Special issue 7th Intern. Conf. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes AAECC-7, Toulouse 1989.

16
I. Z. Emiris, On the complexity of sparse elimination. To appear in J. of Complexity (1996).

17
N. Fitchas and A. Galligo, Nullstellensatz effective et conjecture de Serre (théorème de Quillen-Suslin) pour le calcul Formal. Math. Nachrichten 149, 1990, 231-253.

18
N. Fitchas, M. Giusti and G. Smietanski, Sur la complexité du théoreme des zéros. In Approximation and Optimization 8, ed. J. Guddat et al., Peter Lange Verlag, Frankfurt am Main, 1995, 274-329.

19
T. S. Freeman, G. M. Imirzian, E. Kaltofen &L. Yagati, DAGWOOD - A System for Manipulating Polynomials Given by Straight-Line Programs. ACM Transactions on Mathematical Software 3, 1988, 218-240.

20
M. Giusti &J. Heintz, Un algorithme - disons ``rapide'' - pour la décomposition d'une variété algébrique en composantes irréductibles et équidimensionelles. In Proc. MEGA'90, ed. T. Mora and Carlo Traverso, Birkhäuser Progress in Mathematics vol. 94, 1991, 169 - 194.

21
M. Giusti &J. Heintz, La détermination de la dimension et des points isolés d'une variété algébrique peut se faire en temps polynomial. In Computational Algebraic Geometry and Commutative Algebra Symposia Mathematica, vol. 34, Istituto de Alta Matematica Francesco Severi and Cambridge University Press, Cambridge , 1993, 216-256.

22
M. Giusti, J. Heintz &J. Sabia, On the efficiency of effective Nullstellensätze. Computational Complexity 3, 1993, 56-95.

23
M. Giusti, J. Heintz, J. E. Morais and L. M. Pardo, When polynomial equation systems can be 'solved' fast?. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proc. AAECC-11, eds. G. Cohen, M. Giusti and T. Mora. Lecture Notes in Computer Science 948, Springer Verlag, 1995, 205-231.

24
M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern and L. M. Pardo, Straight-line programs in geometric elimination theory. To appear in J. of Pure and Appl. Algebra, 1996.
25
M. Giusti, J. Heintz &L.M. Pardo, (Eds.) TERA'96. Preprint Depto. de Matemáticas, Est. y Comp. 7, Univ. de Cantabria, 1996.

26
M. Giusti, K. Hägele, J. Heintz, J. L. Montaña, J. E. Morais and L. M. Pardo, Lower Bounds for Diophantine Approximation. To appear in J. of Pure and Appl. Algebra, 1997a.

27
M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo, Le rôle des estructures de données en Théorie de l'Elimination. Preprint, 1997b.

28
D. Yu. Grigor'ev &N. Vorobjov, Solving Systems of Polynomial Inequalities in Subexponential Time. J. of Symb. Comp. 5, 1988, 37-64.

29
A. Grosso, N. Herrera, G. Matera, M.E. Stefanoni &J.M. Turull Torres, A PSPACE implementation of the effective Nullstellensatz. In Proc. JAIIO, Buenos Aires, 1996.

30
K. Hägele, A prototype for straight-line programs, (slp- a C++ classlib) . Preprint, 1996.
31
K. Hägele &G. Matera, Preparatory Note for the Draft for Design and Implementation. Manuscript, 1996.

32
K. Hägele &J.L. Montaña, Polynomial random test for the equivalence problem of integers given by straight-line programs. Preprint, 1996.

33
J. Heintz, Fast quantifier elimination over algebraically closed fields. Theoret. Comput. Sci. 24, 1983, 239-277.

34
J. Heintz, On the computational complexity of polynomials and bilinear mappings. In Proc. AAECC-5, eds. L. Huguet and A. Poli. Lecture Notes in Computer Science 356, Springer Verlag, 1989, 269-300.

35
J. Heintz and J. Morgenstern, On the intrinsic complexity of elimination theory. J. of Complexity 9, 1993, 471-498.

36
J. Heintz, M. F. Roy and P. Solerno, On the complexity of semialgebraic sets. Proc. Information Processing (IFIP'89), San Francisco, G. X. Ritter ed., North Holland, Amsterdam (1989) 293-298.

37
J. Heintz, M. F. Roy and P. Solerno, Sur la Complexité du Principe de Tarski-Seidenberg. Bull. Soc. math. France 118, 1990, 101-126.

38
J. Heintz, M. F. Roy and P. Solerno, Description of the connected components of a semialgebraic set in simply exponential time.Discrete and Computational Geometry 11, 1994, 121-140.

39
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ématique, 1982, 237-254.

40
O.H. Ibarra &S. Moran, Equivalence of Straight-Line Programs. J. of the ACM 30, 1983, 217-228.

41
E. Kaltofen, Greatest common divisor of polynomials given by straight-line programs. J. A. C. M 35 (1) (1988) 234-264.

42
P. Koiran, The Hilbert Nullstellensatz is in the Polynomial Hierarchy. Preprint, 1996.

43
T. Krick and L. M. Pardo, Une approche informatique pour l'approximation diophantienne. C. R. Acad. Sci. Paris 318, Série I, no. 5, 1994, 407-412.

44
T. Krick and L. M. Pardo, A Computational Method for Diophantine Approximation. In Algorithms in Algebraic Geometry and Applications, Proc. MEGA'94, eds. L. Gonzalez-Vega and T. Recio. Progress in Mathematics 143, Birkhäuser Verlag, 1996, 193-254.

45
G. Matera. PhD. thesis, Univ. of Buenos Aires, in preparation, 1997.

46
G. Matera &J.M. Turull Torres, The space complexity of elimination theory. To appear in Proc. Foundations of Computational Mathematics FOCM'97, 1997.

47
E. Mayr and A. Meyer, The complexity of the word problem for commutative semigroups. Advances in Math. 46, 1982, 305-329.

48
J. L. Montaña and L. M. Pardo, Lower bounds for Arithmetic Networks. Appl. Alg. Eng. Comm. Comp. 4, No. 1, 1993, 1-24.

49
L. M. Pardo, How Lower and Upper Complexity Bounds meet in Elimination Theory. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proc. AAECC-11, eds. G. Cohen, M.Giusti &T. Mora. Lecture Notes in Computer Science 948, Springer Verlag, 1995, 33-69.

50
S. Puddu &J. Sabia, An effective algorithm for quantifier elimination over algebraically closed fields using straight -line programs. To appear in J. of Pure and Appl. Algebra, 1997.

51
J. Renegar, On the computational Complexity and Geometry of the First-order Theory of the reals. (Part I: Introduction. Preliminaires. The Geometry of Semi-algebraic sets. The Decision Problem for the Existential Theory of the Reals.) J. of Symb. Computation 13, 1992, 255-301. (also Part II and Part III in the same issue).

52
J.T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities. J. of the ACM 27, 1980, 701-717.

53
A. Schönhage, On the Power of Random Access Machines. In Proceedings of ICALP 6, Lect. Notes Comp. Sci. 71, Springer, 1979.

54
M. Shub, S. Smale, Complexity of Bezout's theorem V: Polynomial time, Theoretical Comp. Sci. 133 (1994)

55
M. Sombra, Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nulstellensatz. To appear in J. Pure Appl. Algebra, 1997.

56
V. Weispfennig,The complexity of linear problems in fields. J. of Symb. Comp. 5, 1988, 3-27.

57
C.K. Yap, A New Lower Bound Construction for Commutative Thue Systems with Applications. J. of Symb. Comp. 12, 1991, 1-27.

58
R. Zippel, Interpolating Polynomials from their Values. J. Symbol. Comput., 9, 1990, 375-403

previous Future progress with TERA

up The Project TERA