Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Research Seminar

Alexey Pospelov: Multiplicative Complexity of Group Algebras

July 9, 2009, 10:15 a.m.
E 1 3, Room 415

Study of multiplicative complexity of group algebras was motivated by recent work by Cohn et. al., who reduce matrix multiplication to multiplication in group algebras. The idea is that if one finds fast multiplication algorithms for certain group algebras they will yield good upper bound for the matrix exponent.

We start with commutative group algebras over arbitrary fields and prove the universal lower Alder-Strassen bound depending only on the dimension of the algebra and the field characteristic. We also describe all commutative group algebras of minimal multiplicative complexity over arbitrary fields and show some algebras of not minimal rank. Next we prove universal linear upper bound for the bilinear complexity and show some applications for multivariate polynomial multiplication and estimation of the rank of 3×3 matrix multiplication over complex and real fields.