Complexity of multiplication in some group algebras
Diskretnaya Matematika, Tome 17 (2005) no. 1, pp. 3-17
Voir la notice de l'article provenant de la source Math-Net.Ru
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},
publisher = {mathdoc},
volume = {17},
number = {1},
year = {2005},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/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/