@inproceedings{B-Algebraische-Komplexitaetstheorie-Ii-Schnelle-Matrixmultiplikation-Und-Kombinatorik,
Title = {Algebraische Komplexitaetstheorie II - Schnelle Matrixmultiplikation und Kombinatorik},
Author = {Peter Bürgisser},
Booktitle = {Seminaire Lotharingien de Combinatoire},
Pages = {1-16},
Year = {1996},
Number = {B36b},
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.},
Url = {http://www3.math.tu-berlin.de/algebra/work/s36buerg.pdf},
Url2 = {http://www.emis.de/journals/SLC/wpapers/s36buerg.html},
Reviewed = {False}
}