*Wissenschaftliches Programm*   *Liste der Vortragenden*

Sektion Plenum
Montag, 18.09.2000, 11.45 Uhr, Audimax, Hörsaalzentrum Bergstraße

Komplexität und Algebra

Volker Strassen, Universität Konstanz

Das Wechselspiel zwischen Komplexitätstheorie und Algebra und damit zwischen theoretischer Informatik und theoretischer Mathematik lässt sich am Beispiel der Multiplikation großer Matrizen besonders sinnfällig machen. Als roten Faden für den Vortrag wählen wir deshalb den sogenannten Exponenten w der Matrixmultiplikation, d. h. die kleinste (infimum) Zahl t mit der Eigenschaft, dass sich n-reihige Matrizen mit O(nt ) arithmetischen Operationen multiplizieren lassen. Die Themenwahl gibt uns Gelegenheit,

  1. die Matrixmultiplikation mit anderen Grundaufgaben der linearen Algebra zu vergleichen, wie die Inversion von Matrizen, die Berechnung von Determinante und charakteristischem Polynom und die Transformation auf geeignete Normalformen,
  2. Techniken zum Beweis unterer Komplexitätsschranken zu erwähnen,
  3. das asymptotische Spektrum als gemeinsamen Fluchtpunkt von Algorithmik und Algebra bilinearer Abbildungen vorzustellen.