Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Computational Complexity - Research Seminar

Alexey Pospelov: Bounds for bilinear complexity of noncommutative group algebras

March 19, 2010, 10:15 a.m.
E 1 3, Room 415

Following a recent attempt by Cohn, Umans et. al. to attack the famous matrix multiplication problem via group algebras and full characterization of complexity of multiplication in commutative group algebras, we study the complexity of multiplication in noncommutative group algebras. We characterize the semisimple group algebras of the minimal bilinear complexity and show nontrivial lower bounds for the rest of the group algebras. These lower bounds are built on the top of Bläser’s results for semisimple algebras and algebras with large radical and the general lower bound for arbitrary associative algebras due to Alder and Strassen. We also show subquadratic upper bounds for all group algebras turning into “almost linear” provided the exponent of matrix multiplication equals 2.