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: