31 KAM Mathematical Colloquium

Prof. Dr. VOLKER STRASSEN

Konstanz

ALGEBRA AND COMPLEXITY

December 4, 1997
Lecture Room S6, Charles University, Malostranske nam. 25, Praha 1
10:30 AM

Abstract

Our discussion of the interplay of Algebra and Complexity will be guided by a ubiquitous computational problem: The multiplication of (large) matrices. This gives us the opportunity to:
  1. compare matrix multiplication with other computational problems of linear algebra,
  2. touch on lower bound techniques of algebraic complexity theory,
  3. introduce the asymptotic spectrum of bilinear maps.
The lecture assumes no mathematical knowledge beyond standard concepts such as "bilinear map between finite dimensional vector spaces" or "compact sets", and no knowledge of computer science at all.