Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-049 | 4th April 2010 12:32

Bounds for Bilinear Complexity of Noncommutative Group Algebras

RSS-Feed




Revision #1
Authors: Alexey Pospelov
Accepted on: 4th April 2010 12:32
Downloads: 2805
Keywords: 


Abstract:

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such 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 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.



Changes to previous version:

Fixed format. Minor changes and some typos fixed.


Paper:

TR10-049 | 24th March 2010 17:04

Bounds for Bilinear Complexity of Noncommutative Group Algebras





TR10-049
Authors: Alexey Pospelov
Publication: 24th March 2010 19:12
Downloads: 2882
Keywords: 


Abstract:

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such 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 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.


Comment(s):

Comment #1 to TR10-049 | 10th April 2010 14:48

Bounds for Bilinear Complexity of Noncommutative Group Algebras

Authors: Alexey Pospelov
Accepted on: 10th April 2010 14:48
Keywords: 


Comment:

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such 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 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.




ISSN 1433-8092 | Imprint