#####
Séminaire Lotharingien de Combinatoire, B36b (1996), 18pp.

# Peter Bürgisser

# Algebraische Komplexitätstheorie II:
Schnelle Matrixmultiplikation und Kombinatorik

**Abstract.**
In 1969 Strassen discovered that Gaussian elimination is not an optimal algorithm
for solving various problems in computational linear algebra. His result was based
on a fast matrix multiplication algorithm needing only
*O*(*n*^{\tau}) arithmetic operations,
where *\tau* < 2.81. The infimum of all possible exponents
*\tau* >= 2 is called the
exponent *\omega* of matrix multiplication. By extending a method by Strassen,
Coppersmith and Winograd showed in 1987 that *\omega* < 2.38.
Today, one even
conjectures that *\omega* = 2.
We survey the main ideas and methods, which have led to such insights about the
complexity of matrix multiplication. In particular, we sketch a simplified version
of Coppersmith and Winograd's proof which is based on a nonconstructive existence
proof for some combinatorial structure.

The following versions are available: