Geodesic
Complexity of multiplication in commutative group algebras over fields of prime characteristic
Diskretnaya Matematika, Tome 22 (2010) no. 4, pp. 121-137 
B. V. Chokaev. Complexity of multiplication in commutative group algebras over fields of prime characteristic. Diskretnaya Matematika, Tome 22 (2010) no. 4, pp. 121-137. http://geodesic.mathdoc.fr/item/DM_2010_22_4_a8/
@article{DM_2010_22_4_a8,
     author = {B. V. Chokaev},
     title = {Complexity of multiplication in commutative group algebras over fields of prime characteristic},
     journal = {Diskretnaya Matematika},
     pages = {121--137},
     year = {2010},
     volume = {22},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2010_22_4_a8/}
}
TY  - JOUR
AU  - B. V. Chokaev
TI  - Complexity of multiplication in commutative group algebras over fields of prime characteristic
JO  - Diskretnaya Matematika
PY  - 2010
SP  - 121
EP  - 137
VL  - 22
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/DM_2010_22_4_a8/
LA  - ru
ID  - DM_2010_22_4_a8
ER  - 
%0 Journal Article
%A B. V. Chokaev
%T Complexity of multiplication in commutative group algebras over fields of prime characteristic
%J Diskretnaya Matematika
%D 2010
%P 121-137
%V 22
%N 4
%U http://geodesic.mathdoc.fr/item/DM_2010_22_4_a8/
%G ru
%F DM_2010_22_4_a8

Voir la notice de l'article provenant de la source Math-Net.Ru

The objective of this research is to study the complexity of multiplication in commutative group algebras over arbitrary fields of prime characteristic. In order to solve this problem, we suggest a method to find the structure of group algebras which allows us to use the Alder–Strassen theorem to obtain lower bounds and the Bläser theorem describing all algebras of minimal rank to obtain upper bounds.

[1] Cohn H., Umans C., “A group-theoretic approach to fast matrix multiplication”, Proc. 44th Annual IEEE Symp. FOCS, IEEE Computer Society, Los Alamitos, CA, 2003, 438–449

[2] Cohn H., Kleinberg R. D., Szegedy B., Umans C., “Group-theoretic algorithms for matrix multiplication”, Proc. 46th Annual IEEE Symp. FOCS, IEEE Computer Society, Los Alamitos, CA, 2005, 379–388

[3] Pospelov A. D., Slozhnost umnozheniya v assotsiativnykh algebrakh, Diss. kand. fiz.-mat. nauk, MGU, 2008

[4] Drozd Yu. A., Kirichenko V. V., Konechnomernye algebry, Vischa shkola, Kiev, 1980 | MR | Zbl

[5] Bürgisser P., Clausen M., Shokrollahi M., Algebraic complexity theory, Springer, Berlin, 1997 | MR | Zbl

[6] Alekseev V. B., “Slozhnost umnozheniya matrits. Obzor”, Kiberneticheskii sbornik, 25, 1988, 189–236 | MR | Zbl

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

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

[9] Bläser M., “Algebras of minimal rank over arbitrary fields”, Lect. Notes Comput. Sci., 2607, 2003, 403–414 | MR | Zbl

[10] Berlekemp E., Algebraicheskaya teoriya kodirovaniya, Mir, Moskva, 1971 | MR

[11] Melnikov O. V., Remeslennikov V. N., Romankov V. A., Skornyakov L. A., Shestakov I. P., Obschaya algebra, v. 1, Nauka, Moskva, 1990

[12] Chudnovsky D., Chudnovsky G., “Algebraic complexities and algebraic curves over finite fields”, J. Complexity, 4 (1988), 285–316 | DOI | MR | Zbl

[13] Bläser M., “Improvements of the Alder–Strassen bound: Algebras with nonzero radical”, Lect. Notes Comput. Sci., 2076, 2001, 79–91 | MR | Zbl