Title :
Algebras of Minimal Multiplicative Complexity
Author :
Bläser, Markus ; Chokaev, Bekhan
Author_Institution :
Dept. of Comput. Sci., Saarland Univ., Saarbrucken, Germany
Abstract :
We prove that an associative algebra A has minimal rank if and only if the Alder-Strassen bound is also tight for the multiplicative complexity of A, that is, the multiplicative complexity of A is 2 dim A - tA where tA denotes the number of maximal twosided ideals of A. This generalizes a result by E. Feig who proved this for division algebras. Furthermore, we show that if A is local or superbasic, then every optimal quadratic computation for A is almost bilinear.
Keywords :
algebra; computational complexity; Alder-Strassen bound; associative algebra; bilinear computation; division algebras; maximal two-sided ideals; minimal multiplicative complexity algebras; minimal rank; optimal quadratic computation; Complexity theory; Computer science; Educational institutions; Polynomials; Vectors; algebraic complexity theory; associative algebra; complexity of bilinear problems;
Conference_Titel :
Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on
Conference_Location :
Porto
Print_ISBN :
978-1-4673-1663-7
DOI :
10.1109/CCC.2012.13
