ECCC-Report TR10-049https://eccc.weizmann.ac.il/report/2010/049Comments and Revisions published for TR10-049en-usSat, 10 Apr 2010 14:48:05 +0300
Comment 1
| Bounds for Bilinear Complexity of Noncommutative Group Algebras |
Alexey Pospelov
https://eccc.weizmann.ac.il/report/2010/049#comment1We 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. Sat, 10 Apr 2010 14:48:05 +0300https://eccc.weizmann.ac.il/report/2010/049#comment1
Revision 1
| Bounds for Bilinear Complexity of Noncommutative Group Algebras |
Alexey Pospelov
https://eccc.weizmann.ac.il/report/2010/049#revision1We 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.Sun, 04 Apr 2010 12:32:57 +0300https://eccc.weizmann.ac.il/report/2010/049#revision1
Paper TR10-049
| Bounds for Bilinear Complexity of Noncommutative Group Algebras |
Alexey Pospelov
https://eccc.weizmann.ac.il/report/2010/049We 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.Wed, 24 Mar 2010 19:12:34 +0200https://eccc.weizmann.ac.il/report/2010/049