Geodesic
Complexity of multiplication in some group algebras
Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 3-17
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, we present some results on algebraic complexity theory, which is a relatively new region of complexity theory. We consider the complexity of multiplication (bilinear complexity) in group algebras. In the 6-dimensional group algebra $\mathbf C(S_3)$ over the field of complex numbers with permutations of the third order as the basis, we find a bilinear algorithm for multiplication with multiplicative complexity equal to 9 (instead of trivial 36) and prove that this bound is unimprovable. We prove a series of assertions on the structure of the group algebra $\mathbf C(S_3)$, in particular, we show that the algebra $\mathbf C(S_3)$ is decomposed into a direct product of the algebra of $2\times 2$ matrices and two one-dimensional algebras. This research was supported by the Russian Foundation for Basic Research, grant 03–01–00783. 
@article{DM_2005_17_1_a0,
     author = {V. B. Alekseev and A. D. Pospelov},
     title = {Complexity of multiplication in some group algebras},
     journal = {Diskretnaya Matematika},
     pages = {3--17},
     year = {2005},
     volume = {17},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2005_17_1_a0/}
}
TY  - JOUR
AU  - V. B. Alekseev
AU  - A. D. Pospelov
TI  - Complexity of multiplication in some group algebras
JO  - Diskretnaya Matematika
PY  - 2005
SP  - 3
EP  - 17
VL  - 17
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2005_17_1_a0/
LA  - ru
ID  - DM_2005_17_1_a0
ER  - 
%0 Journal Article
%A V. B. Alekseev
%A A. D. Pospelov
%T Complexity of multiplication in some group algebras
%J Diskretnaya Matematika
%D 2005
%P 3-17
%V 17
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2005_17_1_a0/
%G ru
%F DM_2005_17_1_a0
V. B. Alekseev; A. D. Pospelov. Complexity of multiplication in some group algebras. Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 3-17. http://geodesic.mathdoc.fr/item/DM_2005_17_1_a0/

[1] Alder A., Strassen V., “On the algorithmic complexity of associative algebras”, Theoret. Comput. Sci., 15 (1981), 201–211 | DOI | MR | Zbl

[2] Bläser M., Algebras of minimal rank over arbitrary fields, SIIM Techn. Rep., May 10, 2002

[3] Van der Varden B. L., Algebra, Nauka, Moskva, 1979 | MR

[4] Vinberg E. B., Kurs algebry, Faktorial Press, Moskva, 2001