TOP
Suche auf der Schloss Dagstuhl Webseite
Sie suchen nach Informationen auf den Webseiten der einzelnen Seminare? - Dann:
Nicht fündig geworden? - Einige unserer Dienste laufen auf separaten Webseiten mit jeweils eigener Suche. Bitte beachten Sie folgende Liste:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminare
Innerhalb dieser Seite:
Externe Seiten:
  • DOOR (zum Registrieren eines Dagstuhl Aufenthaltes)
  • DOSA (zum Beantragen künftiger Dagstuhl Seminare oder Dagstuhl Perspektiven Workshops)
Publishing
Innerhalb dieser Seite:
Externe Seiten:
dblp
Innerhalb dieser Seite:
Externe Seiten:
  • die Informatik-Bibliographiedatenbank dblp


Dagstuhl-Seminar 98241

Real Computation and Complexity

( 15. Jun – 19. Jun, 1998 )

(zum Vergrößern in der Bildmitte klicken)

Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite: https://www.dagstuhl.de/98241

Organisatoren
  • F. Cucker (Barcelona)
  • M. Shub (IBM-Yorktown Heights)
  • M.-F. Roy (Rennes)
  • T. Lickteig (Bonn)



Summary

The field of algorithmic complexity of real computational problems has received much attention in recent years. This topic with geometrical, algebraic, analytic, and numerical aspects encompasses the foundational area of scientific computing and has a wide range of relevant applications. The main object is the computation with polynomials, the better understanding of what makes these computations difficult or easy in order to design faster Computer algebra algorithms. Due to their omnipresence, the case of real polynomials evidently plays a predominant role. Many new algorithms have been designed during the last decade for deciding the existence of solutions of equations and inequalities, or for computing solutions.

The seminar was intended to be broad and open. While clearly focussed on real computational problems, scientists with rather different backgrounds such as computer science, numerical analysis, algebraic geometry, logic, and abstract real algebraic geometry could be brought together to know and discuss main problems from different perspectives. This is important as scientific questions often don't find their answers within their domain of origin. One aim of the seminar was to support the collaboration of people of different origin.

We had 33 participants coming from Belgium, France, Germany, Great Britain, Italy, Poland, Russia, Spain, and the United States. During the meeting 30 lectures have been given that have been continued by informal evening discussions in smaller groups. The talks focussed on new concrete algorithmic results, others introduced to main ongoing work or to the way of looking at things in important neighbouring fields. Main topics addressed include

  • quantitative bounds in real algebraic geometry related to lower and upper complexity bounds,
  • computation schemes (straight line programs) as basic data structure to cope with multivariate polynomial computation,
  • translation of theoretical knowledge into fast implementations, univariate and multivariate root finding and root isolation,
  • BSS discussion of differential equations, other ground fields, and counting problems,
  • exact real computation, and
  • approximation methods in the bit model.

Both, senior researchers as well as young researchers contributed to seminar. A Journal of Complexity (http://www.apnet.com/www/journal/cm.htm) special issue is dedicated to the workshop with selected papers addressing topics covered by this seminar.

The field has two major challenges. The first one, on the theoretical level, is the mathematical understanding of obstructions to the existence of fast polynomial computations, that is to say, lower bounds via an intrinsic inherent geometric complexity of a computational task. By knowing what must be avoided knowledge of lower bounds can furnish a guide-line in the design of algorithms. The second one, the design, is just now going in the direction of putting into effective use the theoretical knowledge of algebraic and arithmetic complexity, that is to say, translation into really real real algorithms that are fast in practice with new basic organisational designs.

We thank the IBFI scientific board for making available to us the Schloss Dagstuhl conference centre. Likewise we express our sincere appreciation of the outstanding organisation of Dagstuhl. On behalf of all participants we thank Dagstuhl for making available support by the TMR program of the European Community funding the participation of young European researchers and keynote speakers.


Teilnehmer
  • F. Cucker (Barcelona)
  • M. Shub (IBM-Yorktown Heights)
  • M.-F. Roy (Rennes)
  • T. Lickteig (Bonn)

Verwandte Seminare
  • Dagstuhl-Seminar 9545: Real Computation and Complexity (1995-11-06 - 1995-11-10) (Details)
  • Dagstuhl-Seminar 04061: Real Computation and Complexity (2004-02-01 - 2004-02-06) (Details)