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: