The Jacques Morgenstern

Challenge

For several years, Jacques Morgenstern and his colleagues have been attempting to understand the relationship between results of Theoretical Computer Science (e.g. worst case lower bounds, the use of straight line programs to represent polynomials, etc.) and the results of Computer Algebra (e.g. solving systems of polynomial equations, quantifier elimination, etc.).

After substantial research and development and notwithstanding the considerable progress made in the mathematical and computer science aspects of the task, one might still ask whether the basic tools of Computer Algebra suffice to “effectively solve large classes of polynomial equations within the near future”. One might even more radically ask whether there exists an intrinsic difficulty, inherent to the problem of solving polynomial equations, which prevents any attempt to generally succeed in the task.

In order to further motivate research and development on the interaction between Computer Algebra and Theoretical Computer Science, and in recognition of the importance of such work to industrial applications, several scientific institutions are sponsoring a challenge, to be called the Jacques Morgenstern Challenge, in which a prize will be offered to the paper (or papers) published during the next five years which make(s) the most convincing argument as to the future success or limitation of Computer Algebra in the context of polynomial systems solving.

For example, exhibiting new and successful Computer Algebra techniques for solving an important family of polynomial systems would be as acceptable as elements contributing to the exact classification of polynomial elimination problems in the hierarchy of space complexity.

The Jacques Morgenstern Challenge is supported by a Promoting Committee consisting of individuals doing active research in Theoretical Computer Science or Computer Algebra (algebraic and semi-algebraic geometry, commutative algebra) and by institutions such as universities and scientific organizations/associations or some of their members. The Promoting Committee tasks are to publicize this Challenge in order to get submissions of high quality, to determine the detailed set up of the Challenge and to request funds from the supporting Institutions in order to offer a total award of US $ 5,000 (five thousand US dollars).

The Promoting Committee will fix the exact deadline for submission and will produce the final announcement by July 1,1995. Moreover it will propose an international jury which will, five years later, award one (or several with the award shared ) paper(s) the prize to be called the Jacques Morgenstern Challenge.

The members of the Promoting Committee will not be elligible for the Prize.

\underline{Provisional Promoting Committee} :

Bernd Bank (Humboldt Univ. Berlin)

Allan Borodin (Univ. Toronto)

Steve Cook (Univ. Toronto)

André Galligo (Univ. Nice)

Marc Giusti (Ecole Polytechnique Palaiseau)

Joos Heintz (Univ. Cantabria/Univ. Buenos Aires)

Juan Llovet (Univ. Alcalá)

Tomás Recio (Univ. Cantabria)

Volker Strassen (Univ. Konstanz)

\underline{Contact Address} :

Tomás Recio, Departamento de Matemáticas Facultad de Ciencias, Universidad de Cantabria –39071– Santander, SPAIN. Telephone : 34-42-201433, Fax: 34-42-201402 E-mail : recio@matsun1.unican.es

\underline{Provisional List of Supporting Institutions} : Ecole Polytechnique, Palaiseau (France) Humboldt Universität, Berlin (Germany) Universidad de Alcalá (Spain) Universidad de Buenos Aires (Argentina) Universidad de Cantabria (Spain)